Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

利用回溯算法，先对num进行升序排序，再进行深搜剪枝。

需要注意遍历num时不能简单地i++,而是要判断num[i]与num[i-1]是否相等，从而避免重复解。

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        vector<vector<int>> re;
        vector<int> thisRe;
        sort(num.begin(), num.end());
        _combinationSum2(0, target, 0, num, thisRe,re);
        return re;
    }
    void _combinationSum2(int sum, int target, int start, vector<int> &num, vector<int>& thisRe, vector<vector<int>>& re){
        if(sum == target){
            re.push_back(thisRe);
            return ;
        }
        else if(start >= num.size()){
            return ;
        }
        else{
            for(int i = start; i < num.size();){
                if(sum + num[i] > target){
                    break;
                }
                else{
                    thisRe.push_back(num[i]);
                    _combinationSum2(sum + num[i], target, i + 1, num, thisRe, re);
                    thisRe.pop_back();
                }
                while(++i < num.size() && num[i] == num[i - 1]){
                    ;
                }
            }
        }
    }
};