Start learning free

LESSON 356 OF 541 · BACKTRACKING

Subsets in Swift: Backtracking with Skip and Take

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 11
    Ctrl + Enter to check

    SWIFT · BACKTRACKING

    Subsets in Swift, explained

    Problem overview

    subsets receives nums, an array of distinct integers, 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 is written in the order its numbers have in nums.

    The order of the subsets is fixed too. The numbers are decided one at a time, and for each number skipping comes before taking. So every subset without nums[0] comes before every subset with it, and inside each group the same rule applies to nums[1], then nums[2], and so on. The empty subset is always first and all of nums is last.

    For nums = [1, 2, 3] the result 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. Among the first four, [] and [3] skip 2 while [2] and [2, 3] take it. For [3, -1] the result is [[], [-1], [3], [3, -1]]: the last subset keeps the order of nums, it isn't sorted.

    Approach: decide about one number at a time

    Every number has two options, skip or take, and the choices are independent, so an array of n numbers has 2^n subsets. A subset is just a string of n choices, like a binary string with 0 for skip and 1 for take. The required order is the order of those strings.

    Backtracking generates them directly. Keep the numbers taken so far in a list current and walk through nums by index. At index i:

    1. Skip nums[i]: continue with index i + 1 and leave current alone.
    2. Take nums[i]: add it to current, continue with index i + 1, then remove it again.

    When the index reaches the end of nums, every number has been skipped or taken, and current is a finished subset: save a copy. Because the skip branch runs before the take branch, the subsets come out in exactly the order the task wants. The removal at the end is the "back" in backtracking: the caller gets current back exactly as it was before the call.

    Step by step

    1. Create result as an empty [[Int]], a list of subsets.
    2. Create current as an empty [Int]: the subset being built. At the start nothing is taken.
    3. Start the search with backtrack(nums, 0, &current, &result). Index 0 is the first number to decide about, and the & lets the call change current and result themselves.
    4. Return result after the call. The helper has added every subset to it.
    5. Write the helper backtrack inside the class. It takes nums, the index i, and current and result as inout parameters.
    6. Base case: check i == nums.count. Past the last index, nothing is left to decide.
    7. Save and stop: inside that if, append current to result and return.
    8. Skip first: call backtrack with i + 1 and leave current as it is. This finds every subset that doesn't contain nums[i].
    9. Take: append nums[i] to current. Numbers are added in index order, so each subset keeps the order of nums.
    10. Recurse again with i + 1. This call finds every subset that contains nums[i].
    11. Undo the choice with current.removeLast(), so the caller sees current unchanged.

    The solution in Swift

    class Solution {
    func subsets(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        var current = [Int]()
        backtrack(nums, 0, &current, &result)
        return result
    }
    func backtrack(_ nums: [Int], _ i: Int, _ current: inout [Int], _ result: inout [[Int]]) {
        if i == nums.count {
            result.append(current)
            return
        }
        backtrack(nums, i + 1, &current, &result)
        current.append(nums[i])
        backtrack(nums, i + 1, &current, &result)
        current.removeLast()
    }
}

    Swift details worth knowing:

    • inout and &. Parameters are constants inside a function. Marking one inout lets the function change the caller's variable, and the caller writes & before the variable to say so. Without inout, calling append on result inside the helper is a compile error.
    • Arrays are values. result.append(current) stores a copy of current as it is at that moment. Later changes to current don't touch the saved subset. After var b = a; b.append(3), a is unchanged.
    • Variable declaration. [[Int]]() and [Int]() create empty arrays of the stated element types. var is needed because they change.
    • Methods calling each other. subsets calls backtrack without a prefix, and the order of the two methods in the class doesn't matter.
    • removeLast() removes and returns the last element. Here the returned value isn't needed, and Swift accepts that for this method without a warning.

    Complexity

    Time: O(n · 2^n). There are 2^n subsets, and saving one copies up to n numbers. The recursion tree has about 2^(n+1) calls, which is smaller than the copying cost.

    Space: O(n) extra, not counting the answer: current holds at most n numbers, and the recursion is n + 1 calls deep.

    Edge cases and common mistakes

    • One number. [0] gives [[], [0]]: without it, then with it. The empty subset is always part of the answer.
    • Forgetting removeLast(). Then current keeps growing across calls, so later subsets contain numbers that were supposed to be skipped.
    • Taking before skipping. Swapping the two branches gives all the right subsets in the wrong order, and the lesson's tests check the order.
    • Saving at every call. Appending current only when i == nums.count gives each subset exactly once. Saving earlier produces duplicates.
    • Sorting the numbers. The subsets keep the order of nums, so [3, -1] has the subset [3, -1], not [-1, 3].
    • Counting. With 4 numbers there are 16 subsets and with 10 numbers there are 1,024, so the largest input in this lesson stays small.

    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]].
    • [5, 6, 7, 8] gives 16 subsets.
    • The numbers 1 to 10 give 1,024 subsets.
    Keep going with Swift500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free