/ Data Structure and Algorithms  

Leetcode 40. Combination Sum II

Question



Similar to Question Leetcode 39. Combination Sum. Only this time the same number in the array can be used once.

Similar Questions

Solution

Solution referenced from here: https://leetcode.com/problems/combination-sum-ii/discuss/16878/Combination-Sum-I-II-and-III-Java-solution-(see-the-similarities-yourself)

The whole algorithm works 99% same as 39. Combination Sum. We only need to make sure that each number is only used once in the result. So how do we achieve that. We can sort the input array and skip the numner if it’s same with previous number.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> results = new ArrayList<>();

    // sort to remove duplicates
    Arrays.sort(candidates);

    backtrack(results, new ArrayList<>(), candidates, target, 0);

    return results;
}

private static void backtrack(List<List<Integer>> results,
                                List<Integer> tempList,
                                int[] candidates,
                                int remaining, 
                                int start) {
    if (remaining < 0) {
        return;
    } else if (remaining == 0) {
        results.add(new ArrayList<>(tempList));
    } else {
        for (int i = start; i < candidates.length; i++) {
            // skip same number
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }

            tempList.add(candidates[i]);

            // start backtrack from i + 1, so we don't visit the same number
            backtrack(results, tempList, candidates, remaining - candidates[i], i + 1);

            // find solution or remaining < 0, backtrack one number in the list
            tempList.remove(tempList.size() - 1);
        }
    }
}