Start learning free

LESSON 355 OF 540 · BACKTRACKING

Subsets in Scala: Backtracking in 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

    SCALA · BACKTRACKING

    Subsets in Scala, explained

    Problem overview

    The method subsets receives an Array[Int] of distinct integers, nums, and returns a List[List[Int]] with every subset: every way to pick some of the numbers, from none (the empty subset) to all of them. Each subset keeps the order the numbers have in nums.

    The order of the result is fixed too. The numbers are decided one at a time, skipping before taking: 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.

    For nums = [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 in front.

    Approach: decide about one number at a time

    A subset is a series of yes/no choices, one per number. With n numbers there are 2^n subsets, so any solution takes at least that long; the work is to produce each one exactly once, in the right order.

    Backtracking does this. Walk through nums by index. At index i, first skip nums(i) and move on to index i + 1. Then take it: add it to the subset being built, move on to i + 1, and afterwards remove it again, so the caller finds the subset as it was. When the index reaches the end, every number has been skipped or taken, and the subset is complete.

    Trying skip before take gives exactly the required order. It is the same as counting in binary: 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.

    For nums = [1, 2] the calls go like this:

    i=0 skip
  i=1 skip
    save List()
  i=1 take 2 -> List(2)
    save List(2)
i=0 take 1 -> List(1)
  i=1 skip
    save List(1)
  i=1 take 2 -> List(1, 2)
    save List(1, 2)

    Step by step

    1. Create result as an empty ArrayBuffer[List[Int]](), a list that can grow. Each subset is itself a list, so it holds lists.
    2. Start the search with backtrack(nums, 0, ArrayBuffer[Int](), result). Nothing is decided yet, so the subset is empty and decisions begin at index 0.
    3. Return result.toList. backtrack fills the same buffer, and toList gives the List the method promises.
    4. Write the helper backtrack with the parameters nums, the index i to decide about, the numbers taken so far in current, and result. It returns Unit.
    5. Check the base case. When i == nums.length, no number is left to decide about.
    6. Save a snapshot with result += current.toList and return. current keeps changing, so the result needs its own copy.
    7. Skip nums(i): call backtrack with i + 1 and current unchanged. This finds every subset without it, and doing it first gives the required order.
    8. Take nums(i): append it to current with +=.
    9. Recurse again with i + 1. This call finds every subset that contains nums(i).
    10. Undo the choice with current.remove(current.length - 1), so current is again what this call received.

    The solution in Scala

    In a file of your own, the code needs import scala.collection.mutable.ArrayBuffer at the top.

    class Solution {
    def subsets(nums: Array[Int]): List[List[Int]] = {
        val result = ArrayBuffer[List[Int]]()
        backtrack(nums, 0, ArrayBuffer[Int](), result)
        result.toList
    }

    def backtrack(nums: Array[Int], i: Int, current: ArrayBuffer[Int], result: ArrayBuffer[List[Int]]): Unit = {
        if (i == nums.length) {
            result += current.toList
            return
        }
        backtrack(nums, i + 1, current, result)
        current += nums(i)
        backtrack(nums, i + 1, current, result)
        current.remove(current.length - 1)
    }
}

    The Scala details worth a closer look:

    • Why the snapshot matters. An ArrayBuffer is mutable, and every recursive call shares the same one. Adding current itself to the result stores a reference, not a copy. By the time the search ends, current is empty again, so a result built that way is eight empty buffers for [1, 2, 3]. current.toList creates a new immutable List with the current numbers, and later changes to the buffer can't touch it.
    • remove takes an index. current.remove(current.length - 1) deletes the element at that position, the last one. It isn't a "remove this value" call: for ArrayBuffer(5, 0, 7), remove(0) deletes the 5 at index 0 and leaves ArrayBuffer(0, 7), while -= 0 deletes the value 0 and leaves ArrayBuffer(5, 7).
    • += on a buffer appends and changes the buffer in place. It is used both for result and for current.
    • Parentheses for indexing. An array element is nums(i), not nums[i].
    • return in a Unit method. The early return ends the call when the subset is complete. The method has no value to hand back, so it is written without one.
    • The final line. result.toList is the last expression of subsets, so it is the method's value.

    Complexity

    Time: O(n · 2^n). There are 2^n subsets, and copying one with toList takes up to n steps. The recursion tree has about 2^(n+1) calls, which is less than the copying cost.

    Space: O(n) extra, not counting the answer. The buffer 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 order inside a subset. For [3, -1] the result is [[], [-1], [3], [3, -1]]. The last subset is [3, -1], in the order of nums, not sorted.
    • Saving current without copying. The result then holds eight empty buffers for [1, 2, 3], as explained above.
    • Forgetting the undo. Without remove, the taken number stays in current for every later call, and the subsets that follow contain numbers they shouldn't.
    • Taking before skipping. Swapping the two calls still finds every subset, but in a different order, and the lesson's tests expect skip first.
    • Counting. For ten distinct numbers the method returns 1024 subsets.

    Testing

    • nums = [1, 2, 3] gives List(List(), List(3), List(2), List(2, 3), List(1), List(1, 3), List(1, 2), List(1, 2, 3)).
    • nums = [0] gives List(List(), List(0)).
    • nums = [3, -1] gives List(List(), List(-1), List(3), List(3, -1)).
    • nums = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] gives a list of 1024 subsets.
    Keep going with Scala500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free