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

Solution:

Use DFS to traverse all possible combinations.

If the sum of combination is larger than target, stop further searching.

If the sum of combination is equal to target, add this combination to result list.

To avoid duplicates, we sort the input array first, and if we find the candidate equals to its previous number and the previous number is not selected, we can not select this candidate.



Code:

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        Arrays.sort(candidates);
        helper(candidates, result, target, new ArrayList<Integer>(), 0);
        return result;
    }
    public void helper(int[] nums, List<List<Integer>> result, int target, List<Integer> list, int pos) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = pos; i < nums.length; i++) {
            if (i != pos && nums[i] == nums[i - 1]) {
                continue;
            }
            list.add(nums[i]);
            helper(nums, result, target - nums[i], list, i + 1);
            list.remove(list.size() - 1);
        }
    }
}