Combination Sum II

Q:
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]

A:

-----------Java-----------recursive--------------------

思路同上------------但是，在不用某个value 的时候，要直接退到后面，直到值不一样。

public class Solution {
    public List<List<Integer>> combinationSum2(int[] A, int target) {
        Arrays.sort(A);
        return helper(A,0,target);
    }
    private List<List<Integer>> helper(int[] A, int start, int target){
        List<List<Integer>>  all = new LinkedList<List<Integer>>();
        if(start>=A.length || target < A[start])
            return all;
        if(target == A[start]){
            List<Integer> list = new LinkedList<Integer>();
            list.add(target);
            all.add(list);
            return all;
        }
        all = helper(A,start+1,target-A[start]);
        for(List<Integer> al : all )
            al.add(0,A[start]);
        
        while(start+1<A.length && A[start+1] == A[start])
            start++;
        all.addAll(helper(A,start+1,target));
        return all;
    }
}

-----------C++  -------iterative ------------

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& C, int target) {
        std::sort(C.begin(), C.end());
        vector<vector<int>> res, tmpRes={{}};
        vector<int> sumList = {0};
        
        for(int i =0;i<C.size(); i++)
        {
            int val = C[i], nVal = 1;
            while( i+1 < C.size() && C[i+1] == val ) // count of current val
            {
                i++;
                nVal++;
            }
            int curCount = tmpRes.size();
            for(int j = 0; j< curCount; ++j)
            {
                auto B = tmpRes[j];
                auto curSum = sumList[j];
                for(int k = 0; k<nVal; k++)
                {
                    B.push_back(val);
                    curSum += val;
                    if (curSum < target){ // add to next round
                        auto C = B; //must create a copy, as B can change next round
                        tmpRes.push_back(C);
                        sumList.push_back(curSum);
                    }else if(curSum == target){
                        res.push_back(B);
                    }
                }
            }            
        }        
        return res;        
    }
};

Learned: