Subsets

The problem

You are given a list of integers, nums, in which no value repeats. Return every subset of it. A subset is what is left when you keep some of the values and drop the others. Keeping none of them gives the empty subset, and keeping all of them gives the whole list; both count. Return each subset exactly once. The subsets may come in any order, and so may the values inside a subset. If nums is empty, its only subset is the empty one, so return a list that holds one empty list.

What to write

function solve(nums: number[]): number[][]

Input
nums = [1,2]

Output
[[1,2],[1],[2],[]]

Input
nums = []

Output
[[]]

Constraints

0–10 distinct integers; output combinations may be in any order.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There are at most 10 values and they are all different, so two different choices of values can never give the same subset. The answer is small enough to write out in full: at most 1,024 subsets. Look at how the count grows: no values give 1 subset, one value gives 2, and two values give 4.

2. Hint 2: Ask a smaller question

   Write subsets of [1, 2, 3] by hand: start with [], then [1], then [1, 2], then [1, 2, 3], adding one value each time. Nothing more can be added. What is the smallest change to your last list that gives a subset you have not written yet?

3. Hint 3: Name the pattern

   The signal is "return every subset": every way to choose among the values. Keep one working subset. Add a value, explore everything that can still be added after it, then take the value out and try the next one. Choosing, exploring and undoing a choice like this is backtracking. Read the lesson on backtracking.

4. Hint 4: State the invariant

   Each call records the subset it is handed and only adds values that come after the last one added. So values always go in from left to right, and each subset can be built in one way only. When a call returns, the working subset is exactly as that call found it.

5. Hint 5: Sketch the pseudocode

   Keep an answer list and one working subset. extend(start): record a copy of the subset. For each position i from start to the end: add the value at i, call extend(i + 1), then remove the value again. Begin with extend(0), then return the answer list.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Record the current subset. Then, for each value from the start position on, add it, recurse from the next position, and remove it again.

The slow way

List the subsets size by size: the empty one, then every single value, then every pair with two nested loops, then every triple with three. Each size needs one more loop inside the others, and you do not know how many values there are when you write the code. Three levels of loops find 15 of the 16 subsets of four values.

The insight

One function that calls itself can stand in for any number of nested loops. Keep one working subset. A call records it, then tries each value that comes after the last one added: add the value, let a deeper call carry on from there, and take the value out again. Adding only later values means each subset is built once, from left to right.

Step by step

1. Keep a list for the answers and one list for the current subset. Every call works on the same current subset, adding a value and taking it out again. The answers list gets a copy each time, because the shared subset keeps changing.
2. Each call first records a copy of the current subset. Every subset counts, whatever its size, so a call records the subset it was handed before adding anything. The first call is handed the empty subset, so that one is recorded too.
3. Try each value from the start position on. Only values after the last one added are offered, so a subset is always built from left to right. That is why [1, 2] is recorded once and never a second time as [2, 1].
4. Add the value and extend the subset from the next position. The deeper call records the longer subset and every subset that grows from that one. The deeper call starts one position past the value added here, so the same value cannot be added twice.
5. Take the value out before trying the next one. All the calls share one list. Removing the value puts the list back exactly as this call found it, so the next value in the loop starts from the same subset.
6. Start at the first position with an empty subset. The first call records the empty subset and may add any value. When the first call returns, every subset has been recorded once, and the list of answers is returned.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Keep a list for the answers and one list for the current subset
  const out = [],
    path = [];
  // 2. Each call first records a copy of the current subset
  function visit(start) {
    out.push([...path]);
    // 3. Try each value from the start position on
    for (let i = start; i < nums.length; i++) {
      // 4. Add the value and extend the subset from the next position
      path.push(nums[i]);
      visit(i + 1);
      // 5. Take the value out before trying the next one
      path.pop();
    }
  }
  // 6. Start at the first position with an empty subset
  visit(0);
  return out;
}

function solve(nums: number[]): number[][] {
  // 1. Keep a list for the answers and one list for the current subset
  const out: number[][] = [],
    path: number[] = [];
  // 2. Each call first records a copy of the current subset
  function visit(start: number): void {
    out.push([...path]);
    // 3. Try each value from the start position on
    for (let i = start; i < nums.length; i++) {
      // 4. Add the value and extend the subset from the next position
      path.push(nums[i]);
      visit(i + 1);
      // 5. Take the value out before trying the next one
      path.pop();
    }
  }
  // 6. Start at the first position with an empty subset
  visit(0);
  return out;
}

def solve(nums):
    # 1. Keep a list for the answers and one list for the current subset
    result = []
    path = []

    # 2. Each call first records a copy of the current subset
    def backtrack(start):
        result.append(path.copy())
        # 3. Try each value from the start position on
        for i in range(start, len(nums)):
            # 4. Add the value and extend the subset from the next position
            path.append(nums[i])
            backtrack(i + 1)
            # 5. Take the value out before trying the next one
            path.pop()

    # 6. Start at the first position with an empty subset
    backtrack(0)
    return result

Example 1, traced

Input
nums = [1,2]

Output
[[1,2],[1],[2],[]]

Why it works

A call records the subset it is handed, then makes one deeper call for each later value. So every recorded list has its values in left to right order, and only one chain of calls leads to it: add its first value, then its second, and so on. Every subset of nums can be written in that order, so each one is recorded exactly once.

Time and space

Time O(n × 2ⁿ), extra space O(n) stack plus O(n × 2ⁿ) output. One call runs per subset, and n values have 2ⁿ subsets: each value is in or out. A call copies up to n values and loops over up to n positions: O(n × 2ⁿ) time. The calls nest at most n + 1 deep, and the answer holds 2ⁿ subsets.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Record a copy of the current subset, not the list itself. Every entry would be the one shared list, which is empty again when the search ends: [1, 2] returns four empty lists.
• Take the value out after its deeper call returns. If the value stays in the shared list, the next value is added on top of it: [1, 2] returns [1, 2, 2] in place of [2].
• Give the deeper call the position after the value you added, not the position after the call's own start. With the start plus 1, a value can be added twice: [1, 2] also returns [2, 2].

Pattern

Backtracking. Builds on Generate Parentheses.

Keep going