Start learning free

LESSON 358 OF 543 · BACKTRACKING

Subsets in Rust: Backtracking with Skip and Take, O(n · 2^n)

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

Given an array nums of distinct integers, return every subset of nums: every way to pick some of its numbers, from none of them (the empty subset) to all of them.

Write the numbers of each subset in the order they have in nums. Return the subsets in the order you get by deciding about the numbers one at a time, skipping before taking: every subset without nums[0] comes before every subset with it; inside each of those two groups, the subsets without nums[1] come before the ones with it, then the same for nums[2], and so on. So the empty subset always comes first, and all of nums comes last.

 

Example 1:

Input: nums = [1,2,3]
Output: [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]
Explanation: The first four subsets skip 1, the last four take it.
Among the first four, [] and [3] skip 2, while [2] and [2,3] take it; in each pair, the one without 3 comes first.
The last four are the same four with 1 in front.

Example 2:

Input: nums = [0]
Output: [[],[0]]
Explanation: With one number there are two subsets: without it, then with it.

Example 3:

Input: nums = [3,-1]
Output: [[],[-1],[3],[3,-1]]
Explanation: The subsets without 3 come first. The last subset is written [3,-1], in the order of nums, not sorted.

 

Constraints:

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All the numbers in nums are distinct.

Note:

The tutorial uses backtracking. Walk through nums one index at a time, keeping the numbers taken so far in a list current. At index i, first skip nums[i]: go on to index i + 1 with current as it is. Then take it: add it to current, go on to index i + 1, and remove it again. When the index reaches the end of nums, every number has been skipped or taken: save a copy of current. Trying skip before take gives exactly the order above. It is the same choice as when you generate binary strings: a subset is a string of n bits, 0 for skip and 1 for take, and the subsets come out in the order of those strings.

There are 2n subsets and copying one takes up to n steps, so the time is O(n · 2n). Besides the answer, the extra space is O(n): the subset being built and one call per index.

STEP 1 OF 10
    Ctrl + Enter to check

    RUST · BACKTRACKING

    Subsets in Rust, explained

    Problem overview

    subsets receives a Vec<i32> of distinct numbers named nums and returns every subset: every way to pick some of the numbers, from none of them (the empty subset) to all of them. Each subset keeps the order the numbers have in nums, and the subsets must come in a fixed order. You decide about the numbers one at a time, and for each number you skip it before you take it. All subsets without nums[0] come before all subsets with it, and inside each group the same rule applies to nums[1], and so on.

    For [1, 2, 3] the answer is:

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

    The first four subsets skip 1 and the last four take it. The last four are the first four with 1 added in front. For [3, -1] the answer is [[], [-1], [3], [3, -1]]: the last subset is written [3, -1], in the order of nums, not sorted.

    Approach: a yes or no for every number

    A subset is a series of yes/no decisions, one for each number: take it or skip it. With n numbers there are 2^n series, so there are 2^n subsets, and any solution has to produce them all. For three numbers that is 8, and for ten it is 1,024.

    Backtracking generates the series with a recursive function. It holds the index i of the number to decide about, and a vector current with the numbers taken so far. At each index it tries both choices:

    1. Skip: go on to index i + 1 with current unchanged.
    2. Take: add nums[i] to current, go on to index i + 1, then remove the number again.

    When i reaches the end of nums, every number was skipped or taken, and current is a finished subset. Trying skip before take gives exactly the order the statement asks for. It is the same order as counting in binary with 0 for skip and 1 for take.

    Step by step

    1. Create result as a mutable Vec::new(). Rust works out its type, Vec<Vec<i32>>, from how it is used below: each subset is a list of numbers, so the result holds lists.
    2. Start the search with Self::backtrack(&nums, 0, &mut Vec::new(), &mut result). Nothing is decided yet, so the index is 0 and the subset being built is a new empty vector. & lends nums for reading, and &mut lends a vector that the call may change.
    3. Return result with no semicolon. backtrack added to this same vector, so it now holds every subset.
    4. Write the helper backtrack with the parameters nums, i (a usize, because it is used as an index), current and result.
    5. Check for the end: if i == nums.len(), no number is left to decide about.
    6. Save a snapshot: result.push(current.clone()), then return. current keeps changing as the search goes on, so the result needs its own copy.
    7. Skip nums[i] by calling backtrack with i + 1 and the same current. Doing this first puts every subset without nums[i] before every subset with it.
    8. Take nums[i] with current.push(nums[i]). Numbers are added in index order, so each subset keeps the order of nums.
    9. Recurse with i + 1 again. This call finds every subset that contains nums[i].
    10. Undo the choice with current.pop(). This is the "back" in backtracking: the caller continues with current exactly as it was before this call.

    The calls for [1, 2, 3] reach the end of nums eight times, and the saved subsets come out in the order shown above.

    The solution in Rust

    impl Solution {
    fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = Vec::new();
        Self::backtrack(&nums, 0, &mut Vec::new(), &mut result);
        result
    }

    fn backtrack(nums: &Vec<i32>, i: usize, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if i == nums.len() {
            result.push(current.clone());
            return;
        }
        Self::backtrack(nums, i + 1, current, result);
        current.push(nums[i]);
        Self::backtrack(nums, i + 1, current, result);
        current.pop();
    }
}

    The Rust details worth a closer look:

    • Why clone(). current is a &mut Vec<i32>, a borrowed vector, while result needs owned Vec<i32> values. Writing result.push(current) does not compile: the compiler reports expected Vec<i32>, found &mut Vec<i32>. current.clone() builds a new vector with the same numbers, which is the snapshot the result keeps.
    • Passing the borrows on. Inside backtrack, nums, current and result are already references, so they are passed to the next call as they are, with no extra & or &mut. Rust reborrows them for the call, so you can use them again afterwards.
    • The starting vector. &mut Vec::new() creates a temporary empty vector and lends it mutably for the call. Nothing else needs it afterwards.
    • Associated functions. backtrack has no self, so it is called as Self::backtrack.
    • Index type. i is a usize, the type Rust requires for indexing and for len(), so i == nums.len() compares two values of the same type.
    • Return value. result has no semicolon, so it is the value subsets returns.

    Complexity

    Time: O(n · 2^n). The recursion has a leaf for each of the 2^n subsets, and about twice as many calls in all. Copying a finished subset takes up to n steps, so the copies cost O(n · 2^n).

    Space: O(n) besides the answer. The vector current holds at most n numbers, and the recursion is at most n + 1 calls deep. The answer itself holds 2^n subsets and is not counted.

    Edge cases and common mistakes

    • One number. [0] gives [[], [0]]: the subset without it, then the subset with it.
    • The empty subset. It is part of the answer, and it comes first, because skipping every number is the first path the recursion finishes.
    • Forgetting pop(). Without the undo, the taken numbers pile up in current. For [1, 2, 3] the output becomes [[], [3], [3, 2], [3, 2, 3], [3, 2, 3, 1], ..., with repeated numbers.
    • Taking before skipping. The subsets are all there but in the wrong order, so the lesson's tests fail.
    • Sorting the numbers. The subsets must follow the order of nums. For [3, -1] the last subset is [3, -1], not [-1, 3].
    • Stopping at nums.len() - 1. The check must be i == nums.len(), so the last number also gets its skip and take. Stopping one step early loses half the subsets.

    Testing

    • [1, 2, 3] gives [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]].
    • [0] gives [[], [0]].
    • [3, -1] gives [[], [-1], [3], [3, -1]].
    • A vector of ten distinct numbers gives 1,024 subsets.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free