Start learning free

LESSON 369 OF 576 · BACKTRACKING

Combination Sum II in Rust: Backtracking with Sorting and Pruning

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

    RUST · BACKTRACKING

    Combination Sum Ii in Rust, explained

    Problem overview

    The function combination_sum2 receives candidates, a vector of positive integers that may contain repeats, and a target. It returns every distinct combination of candidates that adds up to target, as a Vec<Vec<i32>>. Each candidate can be used at most once, so a value 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 they use. With [1, 1, 7] and target 8, the first 1 with the 7 and the second 1 with the 7 are one combination, [1, 7], listed once. The numbers in each combination are in ascending order, and the combinations are in lexicographic order: the first position where two of them differ decides which comes first. When nothing adds up to the target, the result is empty.

    For [10, 1, 2, 7, 6, 1, 5] and target 8, the answer is [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]. For [2, 5, 2, 1, 2] and target 5 it is [[1, 2, 2], [5]], and for [2, 3] and target 4 it is [], because the single 2 cannot be used twice.

    Approach: sort, then choose the next number

    The search tries combinations in a way that never builds the same one twice. Sort candidates first. Equal numbers then sit next to each other, the numbers of every combination come out in ascending order, and the output has the order the task asks for.

    A recursive function gets three pieces of state: start, the first index it may still use, remaining, how much the combination still needs, and current, the combination built so far. When remaining is 0, the numbers in current add up to the target, so a copy is saved. Otherwise a loop tries each index i from start on as the next number: it adds candidates[i], calls itself with i + 1 and with remaining lowered by that number, and then removes the number again.

    Two details do the real work:

    • Skipping repeats. The loop skips candidates[i] when i > start and it equals candidates[i - 1]. Within one call, every turn of the loop should pick a different next value, because a second copy of the same value would lead to exactly the same combinations. At i == start the value is the first one this call tries, so it is taken even when it equals the one before. That is how [1, 1, 6] gets its second 1.
    • Stopping early. The candidates are sorted, so when candidates[i] is bigger than remaining, every later candidate is bigger too. The loop can break instead of checking the rest.

    Recursing with i + 1 is what limits each candidate to one use. A search that recursed with i would allow a number to be picked again and again. With that change, [2, 3] and target 4 would return [[2, 2]], and [10, 1, 2, 7, 6, 1, 5] would give combinations such as [1, 1, 1, 1, 1, 1, 1, 1].

    Step by step

    1. Sort candidates in place with sort(). The parameter is declared mut so the function can change its own vector.
    2. Create result as an empty vector. Rust infers Vec<Vec<i32>> from how it is used.
    3. Start the search with Self::backtrack: a borrow of candidates, start index 0, the whole target still needed, a fresh empty vector for the combination and a mutable borrow of result.
    4. Return result as the last expression.
    5. Declare the helper backtrack with candidates: &Vec<i32>, start: usize, remaining: i32, current: &mut Vec<i32> and result: &mut Vec<Vec<i32>>.
    6. Check for a finished combination. When remaining == 0, the numbers in current add up to exactly the target.
    7. Save a copy and return. Push current.clone() onto result, since current keeps changing. Every candidate is at least 1, so adding anything more would pass the target, and the call can return at once.
    8. Loop i over start..candidates.len(). Starting at start instead of 0 means a combination takes its numbers in index order, so no choice of indexes is built twice.
    9. Skip repeats with continue when i > start and candidates[i] == candidates[i - 1].
    10. Stop when a number is too big. If candidates[i] > remaining, break: the sort guarantees nothing after it fits either.
    11. Choose the number: push candidates[i] onto current.
    12. Recurse with i + 1 as the start and remaining - candidates[i] as the amount still needed.
    13. Undo the choice with current.pop(), so the loop can try the next candidate in its place.

    The solution in Rust

    impl Solution {
    fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        candidates.sort();
        let mut result = Vec::new();
        Self::backtrack(&candidates, 0, target, &mut Vec::new(), &mut result);
        result
    }

    fn backtrack(candidates: &Vec<i32>, start: usize, remaining: i32, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if remaining == 0 {
            result.push(current.clone());
            return;
        }
        for i in start..candidates.len() {
            if i > start && candidates[i] == candidates[i - 1] {
                continue;
            }
            if candidates[i] > remaining {
                break;
            }
            current.push(candidates[i]);
            Self::backtrack(candidates, i + 1, remaining - candidates[i], current, result);
            current.pop();
        }
    }
}

    The Rust details worth a closer look:

    • Borrowing across the recursion. current and result are &mut references, and the recursive call passes them on as they are. Rust reborrows them for the call, so they are usable again as soon as it returns.
    • &mut Vec::new(). It creates a temporary empty vector and lends it mutably for the first call. Nothing else needs it afterwards.
    • current.clone(). It builds a new vector with the same numbers. The result must hold snapshots, because current is changed by the pushes and pops that follow.
    • i - 1 on a usize. It is evaluated only when i > start, which means i is at least 1. The && operator short-circuits, so candidates[i - 1] is never evaluated at i == 0.
    • Plain i32 arithmetic. remaining never goes below zero, because of the break before the subtraction. The bounds in the task keep the sums small.

    Complexity

    Time: O(n * 2^n) in the worst case, for n candidates. There are at most 2^n ways to pick some of them, and copying a combination takes up to n steps. Sorting adds O(n log n). In practice the search is much smaller, because the sort and the break keep it to distinct combinations whose sum stays within the target.

    Space: O(n) beyond the answer. The combination being built and the chain of recursive calls each hold at most one entry per candidate used.

    Edge cases and common mistakes

    • Forgetting to skip repeats. Without the continue line, [1, 1, 7] and target 8 returns [[1, 7], [1, 7]]. On the first example it returns [[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]], and on [2, 5, 2, 1, 2] with target 5 it returns [1, 2, 2] three times.
    • Using i instead of i + 1. That is the rule of the version of the problem where a number can be reused. Here it lets a single 2 stand for [2, 2].
    • Skipping with i > 0. The skip must compare against start. A skip based on i > 0 also blocks the second 1 in [1, 1, 6], even though it is the first number that call tries: the first example then returns [[1, 2, 5], [1, 7], [2, 6]], and [2, 5, 2, 1, 2] with target 5 returns only [[5]].
    • Not sorting. The checks against candidates[i - 1] and the early break both depend on the order, and so does the lexicographic output.
    • A continue where the break belongs. The result would still be right, but the loop would examine candidates that cannot fit.
    • No answer. [4] with target 5 returns [], and [5] with target 5 returns [[5]].
    • Many equal values. [1, 1, 1, 1] with target 2 returns [[1, 1]], exactly one combination despite the many ways to choose two of the four 1s.

    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]].
    • [5], target 5 gives [[5]].
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free