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 sum to target.

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

Note: The solution set must not contain duplicate combinations.

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res =  new ArrayList<>();
        Arrays.sort(candidates);
        dfs(candidates, target, res, new ArrayList<>(), 0);
        return res;   
    }
    
    private void dfs(int[] candidates, int target, List<List<Integer>> res, List<Integer> ans, int start){
        if (target == 0){
            res.add(new ArrayList<>(ans));
        }
        if (target<=0) return;
        
        for (int i=start; i<candidates.length; i++){
            // i>start to make sure duplicated number is allowed in different depth
            // candidates[i]==candidates[i-1] avoid duplication in same depth
            if (i>start && candidates[i]==candidates[i-1]) continue;
            ans.add(candidates[i]);
            dfs(candidates, target-candidates[i], res, ans, i+1);
            ans.remove(ans.size()-1);
        }
    }
}