40 Combination Sum II

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

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

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.
Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> subset = new ArrayList();
        dfs(subset,0,candidates,new ArrayList(),target);
        return subset;
    }  
    
     void dfs( List<List<Integer>> subset,int index,int[] candidates,List<Integer> current, int target){
                 
                 if(target<0)return;
                 if(target==0){
                      subset.add(new ArrayList(current));
                      return;
                 }
         
                for(int i=index;i<candidates.length;i++){
                    if(i>index && candidates[i]==candidates[i-1])continue;
                    current.add(candidates[i]);
                    dfs(subset,i+1,candidates, current,target-candidates[i]);
                    current.remove(current.size()-1);           
                } 
    }