40. Combination Sum II

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.

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

Related issue Subset, Subset II, Combination Sum

one number can be used only once(assuming the set includes duplicates), this is why each generation of dfs start with i+1.

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

        Arrays.sort(num);
        List<Integer> list = new ArrayList<>();
        dfs(num, 0, list, 0, target);

        return res;
    }

    private void dfs(int[] num, int start, List<Integer> list, int sum, int target){
        if(sum == target){
            res.add(new ArrayList<Integer>(list));
            return;
        }

        for(int i=start; i< num.length; i++){
            if(i > start && num[i] == num[i-1]) continue;
            if(num[i] + sum <= target){
                list.add(num[i]);
                dfs(num, i+1, list, sum+num[i], target);
                list.remove(list.size()-1);
            }
        }
    }
}