难度中等
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
解题思路：回溯 + 剪枝
这道题和 39. 组合总和 不同在于这道题不允许在同一个组合内使用同一个数字（注意，这不代表两个值相同的数字），所以我们必须做一些查重处理！强调一下，树层去重的话，需要对数组排序！
具体的参考该视频：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II
写法一：
class Solution {
public:
void backtracking(vector<int>& candidates, int target, int index, int sum, vector<bool>& used)
{
if(sum >= target)
{
// 若等于才进行尾插
if(sum == target)
vv.push_back(v);
return;
}
for(int i = index; i < candidates.size() && sum + candidates[i] <= target; ++i)
{
// used[i - 1]为0代表的是树层之间，为1说明是树枝之间
// 我们只需要判断树层去重的情况
if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false)
continue;
v.push_back(candidates[i]); // 处理
used[i] = true;
backtracking(candidates, target, i + 1, sum + candidates[i], used); // 递归
v.pop_back(); // 回溯
used[i] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int sum = 0;
vector<bool> used(candidates.size(), false);
sort(candidates.begin(), candidates.end()); // 需要先排序
backtracking(candidates, target, 0, sum, used);
return vv;
}
private:
vector<vector<int>> vv;
vector<int> v;
};写法二：(不用used数组的版本)
class Solution {
public:
void backtracking(vector<int>& candidates, int target, int index, int sum)
{
if(sum >= target)
{
// 若等于才进行尾插
if(sum == target)
vv.push_back(v);
return;
}
for(int i = index; i < candidates.size() && sum + candidates[i] <= target; ++i) // 剪枝优化
{
// 判断前后是否会重复，会的话直接continue
// 注意是 i > index，而不是 i > 0，因为有可能有前后相同的值，但是后一个是还没被使用过的比如[1,1,3]这里的前两个1
if(i > index && candidates[i] == candidates[i - 1])
continue;
v.push_back(candidates[i]); // 处理
backtracking(candidates, target, i + 1, sum + candidates[i]); // 递归，为了下一层不能再使用当前值，所以i+1
v.pop_back(); // 回溯
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
int sum = 0;
sort(candidates.begin(), candidates.end()); // 需要先排序
backtracking(candidates, target, 0, sum);
return vv;
}
private:
vector<vector<int>> vv;
vector<int> v;
};