[LeetCode] 40. Combination Sum II

Posted on | In

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:

1
2
3
4
5
6
7
8
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]
]

Example 2:

1
2
3
4
5
6
Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Explanation

  1. We can use backtracking to solve this problem. The base case is target = 0. To improve performance, we can sort the candidates array first, if we encounter a number is greater than the target, then we can break out the loop because we know the numbers after this current number are also greater than the target.

  2. We cannot have duplicate elements, so we can check the element with current index i and its previous element, in other words, candidates[i] and candidates[i-1]. If they are equal, then we ignore it and continue iterate to the next element. Besides this condition, we also need to check current index i and the recursion’s starting index start, if they are not equal and candidates[i] == candidates[i-1], then we ignore this current index and continue the next iterating number. For example:

    1
    2
    3
     candidates = [2, 2', 3]
 2 -> 3 (we want this because index of 2 is start index && 2’ == 2)
 2’ -> 3 (we don’t want this because index of 2' > start index 1 && 2’ == 2)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    void helper(int[] candidates, int target, int start, List<List<Integer>> res, List<Integer> temp) {
        if (target == 0) {
            res.add(new ArrayList<Integer>(temp));
            return;
        } else if (target > 0) {
            for (int i = start; i < candidates.length; i++) {
                if (i > start && candidates[i] == candidates[i-1]) continue;
                if (candidates[i] > target) break;
                temp.add(candidates[i]);
                helper(candidates, target-candidates[i], i+1, res, temp);
                temp.remove(temp.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (candidates == null || candidates.length == 0) return res;
        List<Integer> temp = new ArrayList<>();
        Arrays.sort(candidates);
        helper(candidates, target, 0, res, temp);
        return res;
    }
}