# 组合总和 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]]
给定一个数组 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;
}
};
```