题目

给定一个候选人编号的集合 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]
]

分析

子集和组合类问题类似,区别是返回条件不一样,子集可继续生长无需返回,组合达到终止条件直接返回结果,或者不可能达到target提前终止.
至于终止条件可以类似于trace原因跟踪遍历过程
算法框架:

选择列表排序
路径列表
路径
target
void backtrack(选择列表) {
	if target 合格:
		路径列表.add(路径)
		return //组合
		//return //因为子集还能生长
	if target 不可能:
		return //提前终止
	for 选择 in 选择列表[start:]:
		if 选择 > start && 选择列表[选择]==选择列表[选择-1]:
			continue //与前一个相同的树枝剪掉
		路径.add(选择)
		target+=选择
		backtrack(选择列表,选择+1)
		路径.pop(选择) //重新进行下一个选择
		target-=选择
}

C++代码

class Solution {
private:
    vector<int> _trace;
    int _sum;
    vector<vector<int>> _results;
    void backtrack(const vector<int>& nums, const int& start,const int& target){
        if(_sum==target){
            _results.push_back(_trace);
            return;
        }
        if(_sum>target)
            return;//提前终止
        for(int i=start;i<nums.size();i++){
            if(i>start&& nums[i]==nums[i-1])
                continue;
            _trace.push_back(nums[i]);
            _sum+=nums[i];
            backtrack(nums,i+1,target);
            _trace.pop_back();
            _sum-=nums[i];
        }
    }
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end(),[](int a,int b){return a<b;});
        _sum=0;
        backtrack(candidates,0, target);
        return _results;
    }
};