L40. Combination Sum II

Problem:

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

Solution:

• sort function will be easier to deal with the duplicates

• i+1 so would not be use the num again

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