# 组合总和 II

给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明:

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[[1, 7],[1, 2, 5],[2, 6],[1, 1, 6]]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[[1,2,2],[5]]

以下错误的选项是?

## aop ### before ```cpp #include using namespace std; ``` ### after ```cpp int main() { Solution sol; vector> res; vector candidates = {10, 1, 2, 7, 6, 1, 5}; int target = 8; res = sol.combinationSum2(candidates, target); for (auto i : res) { for (auto j : i) cout << j << " "; cout << endl; } return 0; } ``` ## 答案 ```cpp class Solution { public: vector> combinationSum2(vector &candidates, int target) { vector temp; vector> result; sort(candidates.begin(), candidates.end()); getans(candidates, target, 0, result, temp); return result; } void getans(vector candidates, int target, int start, vector> &result, vector temp) { if (target == 0) { result.push_back(temp); } else if (target > 0) { int k = candidates.size() - 1; while (target < candidates[k]) k--; for (int i = start; i <= k; i++) { if (i != start && candidates[i] == candidates[i - 1]) continue; temp.push_back(candidates[i]); getans(candidates, target, i, result, temp); temp.pop_back(); } } } }; ``` ## 选项 ### A ```cpp class Solution { public: vector> combinationSum2(vector &candidates, int target) { vector> res; sort(candidates.begin(), candidates.end()); dfs(candidates, 0, target, res); return res; } private: vector stack; void dfs(vector &candidates, int start, int target, vector> &res) { if (target < 0) { return; } else if (target == 0) { res.push_back(stack); } else { int last = INT_MIN; for (int i = start; i < candidates.size(); i++) { if (last != candidates[i]) { stack.push_back(candidates[i]); dfs(candidates, i + 1, target - candidates[i], res); stack.pop_back(); } last = candidates[i]; } } } }; ``` ### B ```cpp class Solution { public: vector> combinationSum2(vector &candidates, int target) { vector> res; vector temp; backtrace(candidates, temp, 0, target); res.assign(m_set.begin(), m_set.end()); return res; } void backtrace(vector &candidates, vector &temp, int index, int target) { if (target == 0) { sort(temp.begin(), temp.end()); /* 去重 */ m_set.insert(temp); return; } /* 设定边界*/ if (index == candidates.size()) { return; } if (target >= candidates[index]) { vector tmp(temp); tmp.push_back(candidates[index]); backtrace(candidates, tmp, index + 1, target - candidates[index]); } backtrace(candidates, temp, index + 1, target); } private: set> m_set; }; ``` ### C ```cpp class Solution { public: void dfs(vector> &ans, vector &candidates, vector &tmp, int target, int start) { if (target == 0) { ans.push_back(tmp); return; } else if (target < 0) { return; } else { for (int i = start; i < candidates.size(); i++) { tmp.push_back(candidates[i]); dfs(ans, candidates, tmp, target - candidates[i], i + 1); tmp.pop_back(); while (i + 1 < candidates.size() && candidates[i] == candidates[i + 1]) i++; } } } vector> combinationSum2(vector &candidates, int target) { vector> ans; vector tmp; if (candidates.empty()) return ans; sort(candidates.begin(), candidates.end()); dfs(ans, candidates, tmp, target, 0); return ans; } }; ```