另一种跳过的实现:使用一个map对重复的数字个数进行统计(这样做将会导致空间复杂度的上升,当数据量巨大时将会导致大量的内存占用),对于当数值 cur 一次处理完全部的选取情况,假设当前数值 cur 总共有n个,那么分别尝试选取 0-n个的选取方式进行递归,当 cur 移动到下一个位置时必然不存在重复元素。
public: voiddfs(int pos, int rest){ if (rest == 0) { ans.push_back(sequence); return; } if (pos == freq.size() || rest < freq[pos].first) { return; }
dfs(pos + 1, rest);
int most = min(rest / freq[pos].first, freq[pos].second); // 使用min处理进行剪枝 for (int i = 1; i <= most; ++i) { sequence.push_back(freq[pos].first); dfs(pos + 1, rest - i * freq[pos].first); } for (int i = 1; i <= most; ++i) { // 最终必然是尝试了most个,全部回溯 sequence.pop_back(); } }
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(), candidates.end()); for (int num: candidates) { if (freq.empty() || num != freq.back().first) { freq.emplace_back(num, 1); } else { ++freq.back().second; } } dfs(0, target); return ans; } };