Start learning free

LESSON 366 OF 573 · BACKTRACKING

Combination Sum II in TypeScript: Sorted Backtracking, No Duplicates

Practice O(n · 2n) Read the full explanation

Given an array of integers candidates, which may contain duplicates, and an integer target, return every distinct combination of candidates that adds up to target.

Each candidate may be used at most once in a combination, so a number that appears twice in candidates can appear up to twice in one combination. Two combinations are the same when they hold the same numbers the same number of times, whichever copies of a repeated number they use: in [1,1,7] with target = 8, the first 1 with the 7 and the second 1 with the 7 are one combination, [1,7], and it must appear only once.

Write the numbers of each combination in ascending order, and return the combinations in lexicographic order: compare two combinations number by number, and the first position where they differ decides which one comes first. This is the order in which the search described in the note below finds them. If no combination adds up to target, return an empty array.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: Sorted, the candidates are [1,1,2,5,6,7,10]. [1,1,6] uses both 1s.
[1,7] can be made with either 1, but it is listed once. [1,2,5] comes before [1,7] because at the second number, 2 is smaller than 7.

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]
Explanation: There are three 2s; [1,2,2] uses two of them and appears once. 5 alone is 5.

Example 3:

Input: candidates = [2,3], target = 4
Output: []
Explanation: 2 + 3 = 5 is too much, and the 2 can't be used twice, so no combination adds up to 4.

 

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

Note:

The tutorial uses backtracking, as in Combination Sum. Sort candidates. A call gets start, the first index it may still use, remaining, what the combination still needs, and current, the combination built so far. When remaining is 0, it saves a copy of current. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], calls itself with i + 1 and remaining - candidates[i], and removes the number again. Because the candidates are sorted, the loop can stop at the first one that is bigger than remaining.

Two things change from Combination Sum. First, the deeper call starts at i + 1, not at i: there, a number could be chosen again and again; here, each candidate is used at most once. Second, as in Subsets II, the loop skips candidates[i] when i > start and it equals candidates[i - 1]. Inside one call, every turn of the loop picks a different next number, and a second copy of the same value would build exactly the same combinations again. A copy is still taken when it is the first one this call tries, at i = start: that is how [1,1,6] gets its second 1.

The search is exponential: with n candidates, there are at most 2n ways to pick some of them, and copying a combination takes up to n steps, so the time is O(n · 2n) in the worst case. The sorted order keeps it far smaller in practice: the calls only build distinct combinations whose sum is at most target. Besides the answer, the extra space is O(n): the combination being built and one call per number in it.

STEP 1 OF 13
    Ctrl + Enter to check

    TYPESCRIPT · BACKTRACKING

    Combination Sum Ii in TypeScript, explained

    Problem overview

    The method combinationSum2 receives candidates, an array of positive integers that may repeat, and a target. It returns every distinct combination of candidates that adds up to target. Each candidate is used at most once, so a value that appears twice in the array can appear up to twice in one combination. Two combinations are the same when they hold the same values the same number of times, whichever copies they use.

    Each combination is written in ascending order, and the combinations come in lexicographic order: compare number by number, and the first difference decides. When nothing adds up to target the answer is an empty array.

    For candidates = [10, 1, 2, 7, 6, 1, 5] and target = 8, the sorted candidates are [1, 1, 2, 5, 6, 7, 10] and the answer is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. The combination [1, 7] can be made with either 1, yet it is listed once. For [2, 3] with target 4 the answer is []: 2 + 3 is 5, and the single 2 can't be used twice.

    Approach: sort, choose the next number, skip repeated values

    The search builds a combination one number at a time. A call receives start, the first index it may still use, remaining, the amount the combination still needs, and current, the combination so far. When remaining is 0, current adds up to the target, so the call saves a copy. Otherwise a loop tries each index i from start as the next number: add candidates[i], call itself with i + 1 and the smaller remaining, then remove the number again.

    Three details make it correct and fast.

    • Sorting. Sorted candidates give ascending combinations, the required order, and make equal values neighbours.
    • The deeper call starts at i + 1. A call that started at i would be allowed to pick the same candidate again and again, which is a different problem. Starting after i uses each candidate at most once.
    • Skipping repeated values inside one loop. Every turn of a loop picks a different next number. If candidates[i] equals candidates[i - 1] and i > start, that value was already tried as the next number in this call, and trying it again would build the same combinations a second time. Without this rule, the first example returns [[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]], with [1, 2, 5] and [1, 7] twice.

    The condition is i > start, not i > 0. At i = start the number is the first this call tries, so it is taken even when it equals its left neighbour. That is how [1, 1, 6] gets its second 1. With i > 0 the same input returns [[1, 2, 5], [1, 7], [2, 6]], and [1, 1, 6] is lost.

    The sorted order has one more use. Candidates are at least 1, and once candidates[i] is bigger than remaining, every later candidate is bigger still. The loop can stop there with break.

    Step by step

    1. Sort candidates in place with sort((a, b) => a - b). Without the comparison, sort compares numbers as text and puts 10 before 2.
    2. Create result as an empty number[][].
    3. Start the search at index 0 with target still needed and an empty combination.
    4. Return result, filled in place by the search.
    5. Write the helper backtrack(candidates, start, remaining, current, result), returning void.
    6. Check for a finished combination: if remaining === 0, the numbers in current add up to the target.
    7. Save a copy with [...current] and return. Adding anything more would pass the target, since every candidate is at least 1.
    8. Loop from start to the end of the array.
    9. Skip repeats: if i > start and candidates[i] === candidates[i - 1], continue.
    10. Stop when too big: if candidates[i] > remaining, break.
    11. Choose the number: push it onto current.
    12. Recurse with i + 1 and remaining - candidates[i].
    13. Undo with current.pop(), so the loop can try the next candidate.

    The solution in TypeScript

    class Solution {
    combinationSum2(candidates: number[], target: number): number[][] {
        candidates.sort((a, b) => a - b);
        const result: number[][] = [];
        this.backtrack(candidates, 0, target, [], result);
        return result;
    }

    backtrack(candidates: number[], start: number, remaining: number, current: number[], result: number[][]): void {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }
            if (candidates[i] > remaining) {
                break;
            }
            current.push(candidates[i]);
            this.backtrack(candidates, i + 1, remaining - candidates[i], current, result);
            current.pop();
        }
    }
}

    TypeScript details:

    • Copying with [...current]. Arrays are objects, and current is the same array in every call. Pushing it directly would store a reference that is emptied again by the later pop() calls. The spread builds a new array with the current numbers.
    • continue and break. continue ends this turn of the loop and moves to the next i. break leaves the loop completely. Using continue for the too-big check would still be correct but would keep looking at numbers that can't fit.
    • sort mutates its argument. The array the caller passed ends up sorted.
    • Erased types. The annotations are checked by the compiler and removed from the JavaScript, so they never convert anything at run time.
    • Method calls need this. Inside the class the helper is called as this.backtrack(...).

    Complexity

    Time: O(n · 2^n) in the worst case. With n candidates there are at most 2^n ways to pick some of them, and copying a combination takes up to n steps. In practice it is far less: sorting and the break mean the search only extends combinations whose sum is still at most the target, and the repeat rule means each distinct combination is reached once. For example, 100 candidates made of two copies of each of 1 to 50, with target 30, take 7,330 calls and return 1,225 combinations.

    Space: O(n) besides the answer. The combination under construction and the recursion both hold at most n numbers.

    Edge cases and common mistakes

    • No combination. [2, 3] with target 4 gives [], because the lone 2 can't be reused.
    • Several copies. [2, 5, 2, 1, 2] with target 5 gives [[1, 2, 2], [5]]. Three 2s are available, and the combination uses two of them, once.
    • Copies of the same value only. [1, 1, 1, 1] with target 2 gives [[1, 1]], a single combination, though there are six ways to choose two of the four 1s.
    • Another mix. [3, 1, 3, 5, 1, 1] with target 8 gives [[1, 1, 1, 5], [1, 1, 3, 3], [3, 5]].
    • Reusing a candidate. Passing i instead of i + 1 in the recursive call lets one candidate repeat. For [2, 3] with target 4 it would return [[2, 2]], which is wrong here.
    • Using i > 0 in the skip rule. It removes combinations that use equal values, as shown above.
    • Dropping the skip rule. It returns duplicate combinations.
    • Sorting as text. The default sort() would order 10 before 2 and break both the ascending order and the break test.

    Testing

    • [10, 1, 2, 7, 6, 1, 5], target 8, gives [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]].
    • [2, 5, 2, 1, 2], target 5, gives [[1, 2, 2], [5]].
    • [2, 3], target 4, gives [].
    • [1, 1, 7], target 8, gives [[1, 7]].
    • [1, 1, 1, 1], target 2, gives [[1, 1]].
    • [3, 1, 3, 5, 1, 1], target 8, gives [[1, 1, 1, 5], [1, 1, 3, 3], [3, 5]].
    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free