Question:

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, a1 ≤ a2 ≤ … ≤ ak).
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]

Thinking:

We should use backtracing to trace all the possible answers. In order to remove duplicate, there are two methods. One is to use hashset, the other is to build a visited array, if the same value is not visited, then don’t visit the value. And there two ways to backtracing, one is to use the return value, and the other is to pass the fucntion value.

Solution1:

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    return backtracing(candidates, target, 0);
}

public List<List<Integer>> backtracing(int [] candidates, int target, int left){
    HashSet<List<Integer>> tres = new HashSet<List<Integer>>();
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    int right = candidates.length-1;

    if (left > right){
        return res;
    }
    if (target < candidates[left]){
        return res;
    }
    if (target == candidates[left]){
        List<Integer> list = new ArrayList<Integer>();
        list.add(candidates[left]);
        res.add(list);
        return res;
    }
    if (left == right){
        return res;
    }

    for (int i = left; i <= right; i++){
        for (List<Integer> list: backtracing(candidates, target-candidates[i], i+1)){
            list.add(0, candidates[i]);
            tres.add(list);
        }
        for (List<Integer> list: backtracing(candidates, target, i+1)){
            tres.add(list);
        }
    }

    res.addAll(tres);
    return res;
}

Solution2:

public static ArrayList<List<Integer>> combinationSum2(int[] candidates, int target) {  
    ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();  
    ArrayList<Integer> item = new ArrayList<Integer>();
    if(candidates == null || candidates.length==0)  
        return res; 

    Arrays.sort(candidates);  
    boolean [] visited = new boolean[candidates.length];
    helper(candidates,target, 0, item ,res, visited);  
    return res;  
}  

private static void helper(int[] candidates, int target, int start, List<Integer> item,   
ArrayList<List<Integer>> res, boolean[] visited){  
    if(target<0)  
        return;  
    if(target==0){  
        res.add(new ArrayList<Integer>(item));  
        return;
    }

    for(int i=start;i<candidates.length;i++){
        if(!visited[i]){
            if(i>0 && candidates[i] == candidates[i-1] && visited[i-1]==false)//deal with dupicate
                continue;  
            item.add(candidates[i]);
            visited[i]=true;
            int newtarget = target - candidates[i];
            helper(candidates,newtarget,i+1,item,res,visited);  
            visited[i]=false;
            item.remove(item.size()-1);  
        }
    }  
}