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 (a1, a2, � , ak) must be in non-descending order. (ie, a…

LeetCode-Combination Sum II

C++:
class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &candidates, int target) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> results;
        if(candidates.size()==0) return results;
        sort(candidates.begin(),candidates.end());
        vector<int> result;
        comb(candidates,target,results,result,0,0);
        return results;
    }
    void comb(vector<int> candidates,int target,vector<vector<int>> &results,vector<int> &result,int start,int num){
        if(num==target){
            results.push_back(result);
            return;
        }
        for(int i=start;i<candidates.size();i++){
            if(i>start&&candidates[i]==candidates[i-1]) continue;
            if(num+candidates[i]<=target){
                result.push_back(candidates[i]);
                comb(candidates,target,results,result,i+1,num+candidates[i]);
                result.pop_back();
            }else break;
        }
    }
};
Java:
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
        if(candidates==null||candidates.length==0) return results;
        Arrays.sort(candidates);
        ArrayList<Integer> result=new ArrayList<Integer>();
        comb(candidates,target,results,result,0,0);
        return results;
    }
    public void comb(int[] candidates,int target,ArrayList<ArrayList<Integer>> results,ArrayList<Integer> result,int start,int num){
        if(num==target){
            ArrayList<Integer> cur=new ArrayList<Integer>();
            for(Integer i:result) cur.add(i);
            results.add(cur);
            return;
        }
        for(int i=start;i<candidates.length;i++){
            if(i>start&&candidates[i]==candidates[i-1]) continue;
            if(num+candidates[i]<=target){
                result.add(candidates[i]);
                comb(candidates,target,results,result,i+1,num+candidates[i]);
                result.remove(result.size()-1);
            }else break;
        }
    }
}