方法：回溯
解题思路
- 如何去重？
- 答：对相同的元素进行统一的处理，即枚举当前操作选几个该元素。
代码
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<pair<int, int>> unique_seq;
for (auto &num : candidates) {
if (unique_seq.empty() || num != unique_seq.back().first) {
unique_seq.emplace_back(num, 1);
} else {
unique_seq.back().second ++ ;
}
}
int n = unique_seq.size();
vector<vector<int>> ans;
vector<int> cur;
function<void(int, int)> dfs = [&](int pos, int sum) -> void {
if (sum == target) ans.emplace_back(cur);
if (pos == n || target - sum < unique_seq[pos].first) return ;
dfs(pos + 1, sum);
int num = unique_seq[pos].first, cnt = unique_seq[pos].second;
int most = min((target - sum) / num, cnt);
for (int i = 1; i <= most; i ++ ) { // 枚举
cur.push_back(num);
dfs(pos + 1, sum + i * num);
}
for (int i = 1; i <= most; i ++ ) {
cur.pop_back();
}
};
dfs(0, 0);
return ans;
}
};
复杂度分析
时间复杂度：\(O(2^n * n)\)；
空间复杂度：\(O(n)\)。