mediumBacktracking

Combination Sum II

Find distinct combinations that sum to the target. Each input position may be used at most once, and duplicate values may occur.

LeetCode ↗

Work through the cases

3 examples

Input notation

Positive values on line 1; positive target on line 2.

Expected result

Sorted combinations in lexicographic order, as bracketed comma-separated lists; or none.

Case 1

Input

1 1 2 3
4

Expected output

[1,1,2]
[1,3]

Case 2

Input

2 2
3

Expected output

none

Case 3

Input

1 1 1
2

Expected output

[1,1]

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Unlike the previous problem, each number may be used only once, and candidates may contain duplicates. Without deduping, the same multiset is found via different index combinations. n ≤ 100 and target ≤ 30 make pruning even more important. Sort so equal values sit together. At the same depth, if j \gt i and candidates[j] equals the previous value, that value has already been tried as “this level’s choice” and we skip it. The recursive call is dfs(j+1,\ldots): this index cannot be reused. If the remainder s is already smaller than the current value, the whole branch stops.

We can first sort the array to facilitate pruning and skipping duplicate numbers.

Next, we design a function dfs(i, s), which means starting the search from index i with a remaining target value of s. Here, i and s are both non-negative integers, the current search path is t, and the answer is ans.

In the function dfs(i, s), we first check whether s is 0. If it is, we add the current search path t to the answer ans, and then return. If i ≥ n or s \lt candidates[i], the path is invalid, so we return directly. Otherwise, we start the search from index i, and the search index range is j \in [i, n), where n is the length of the array candidates. During the search, if j \gt i and candidates[j] = candidates[j - 1], it means that the current number is the same as the previous number, we can skip the current number because the previous number has been searched. Otherwise, we add the current number to the search path t, recursively call the function dfs(j + 1, s - candidates[j]), and after the recursion ends, we remove the current number from the search path t.

We can also change the implementation logic of the function dfs(i, s) to another form. If we choose the current number, we add the current number to the search path t, then recursively call the function dfs(i + 1, s - candidates[i]), and after the recursion ends, we remove the current number from the search path t. If we do not choose the current number, we can skip all numbers that are the same as the current number, then recursively call the function dfs(j, s), where j is the index of the first number that is different from the current number.

In the main function, we just need to call the function dfs(0, target) to get the answer.

The time complexity is O(2^n × n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n × n).

Similar problems:

- 39. Combination Sum - 77. Combinations - 216. Combination Sum III

class Solution {
    private List<List<Integer>> ans = new ArrayList<>();
    private List<Integer> t = new ArrayList<>();
    private int[] candidates;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        this.candidates = candidates;
        dfs(0, target);
        return ans;
    }

    private void dfs(int i, int s) {
        if (s == 0) {
            ans.add(new ArrayList<>(t));
            return;
        }
        if (i >= candidates.length || s < candidates[i]) {
            return;
        }
        for (int j = i; j < candidates.length; ++j) {
            if (j > i && candidates[j] == candidates[j - 1]) {
                continue;
            }
            t.add(candidates[j]);
            dfs(j + 1, s - candidates[j]);
            t.remove(t.size() - 1);
        }
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.