Subsets II

The problem

You are given a list of integers, nums, in which a value may appear more than once. Return every different subset of it. A subset is what is left when you keep some of the values and drop the others; keeping none gives the empty subset. Two subsets are the same when they hold the same values the same number of times, so in [1, 2, 2] keeping the first 2 or the second 2 gives one subset, [2], which is listed once. The subsets may come in any order, and so may the values inside a subset.

What to write

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

Input
nums = [1,2,2]

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

Input
nums = [0]

Output
[[],[0]]

Constraints

Input may contain duplicates; 1 ≤ nums.length ≤ 10.

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, so at most 1,024 subsets, few enough to write out. But values can repeat, and then different choices of positions give the same subset: in [1, 2, 2], keeping the first 2 or the second 2 both give [2]. Each different subset must appear once.

2. Hint 2: Ask a smaller question

   List the subsets of [2, 2] by choosing positions: neither, the first, the second, or both. Two of the four results are the same list. Which one choice could you forbid so that the repeat is never written, while [2, 2] still is?

3. Hint 3: Name the pattern

   The signal is "return every different subset". The plan for a list without repeats still works: record the current subset, add a value, explore, take the value out. That is backtracking. Repeated values are the new part. Sort first, so that equal values end up next to each other and a repeat is easy to spot. Read the lesson on backtracking.

4. Hint 4: State the invariant

   Among the values a call can add next, it uses only the first of each group of equal values. Adding the second 2 in the same place would rebuild subsets that the first 2 already gave. A deeper call may still add that second 2, which is how [2, 2] appears.

5. Hint 5: Sketch the pseudocode

   Sort nums. Keep an answer list and one working subset. extend(start): record a copy of the subset. For each position i from start on: if i is past start and the value at i equals the value at i - 1, skip it. Otherwise add the value, call extend(i + 1) and remove the value. Begin with extend(0).

Solution

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

Approach

Sort first and skip equal sibling choices at each recursion depth. Equal values may still be chosen at deeper levels.

The slow way

Build every subset as if all the values were different, then sort each one and remove those you have already seen. It is correct, but it builds lists only to delete them, and comparing whole lists is extra work. [1, 2, 2] gives 8 lists to keep 6, and ten equal values give 1,024 lists to keep 11.

The insight

A repeat appears only when two equal values compete for the same place in a subset. After sorting, equal values are neighbors, so that moment is easy to see: the loop is about to try a value equal to the one it tried a moment ago. Skip it there. Deeper down the same value is still welcome, so a subset can hold it several times.

Step by step

1. Sort the values so that equal ones sit next to each other. The skip further down compares a value only with its left neighbor. That catches every repeat only if equal values sit side by side, as in [0, 4, 4] and not in [4, 0, 4].
2. 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.
3. Each call first records a copy of the current subset. Every subset counts, not only the longest ones, so a call records what it was handed before it adds anything. The start position tells the call which values it may still add.
4. 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 and never in two different orders.
5. Skip a value equal to the one before it in the same loop. The loop already tried an equal value in this place, along with everything that can follow it. Trying its twin here would build the same subsets a second time.
6. Add the value, extend from the next position, take the value out. The deeper call starts right after this value, so it may add an equal value that follows: that is how [2, 2] is built. Taking the value out lets the loop try another value in this place.
7. Start at the first position with an empty subset. The first call records the empty subset and may add any value. When it returns, every different subset has been recorded once.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Sort the values so that equal ones sit next to each other
  nums.sort((a, b) => a - b);
  // 2. Keep a list for the answers and one list for the current subset
  const out = [],
    path = [];
  // 3. Each call first records a copy of the current subset
  function visit(start) {
    out.push([...path]);
    // 4. Try each value from the start position on
    for (let i = start; i < nums.length; i++) {
      // 5. Skip a value equal to the one before it in the same loop
      if (i > start && nums[i] === nums[i - 1]) continue;
      // 6. Add the value, extend from the next position, take the value out
      path.push(nums[i]);
      visit(i + 1);
      path.pop();
    }
  }
  // 7. Start at the first position with an empty subset
  visit(0);
  return out;
}

function solve(nums: number[]): number[][] {
  // 1. Sort the values so that equal ones sit next to each other
  nums.sort((a, b) => a - b);
  // 2. Keep a list for the answers and one list for the current subset
  const out: number[][] = [],
    path: number[] = [];
  // 3. Each call first records a copy of the current subset
  function visit(start: number): void {
    out.push([...path]);
    // 4. Try each value from the start position on
    for (let i = start; i < nums.length; i++) {
      // 5. Skip a value equal to the one before it in the same loop
      if (i > start && nums[i] === nums[i - 1]) continue;
      // 6. Add the value, extend from the next position, take the value out
      path.push(nums[i]);
      visit(i + 1);
      path.pop();
    }
  }
  // 7. Start at the first position with an empty subset
  visit(0);
  return out;
}

def solve(nums):
    # 1. Sort the values so that equal ones sit next to each other
    nums.sort()
    # 2. Keep a list for the answers and one list for the current subset
    result = []
    path = []

    # 3. Each call first records a copy of the current subset
    def backtrack(start):
        result.append(path.copy())
        # 4. Try each value from the start position on
        for i in range(start, len(nums)):
            # 5. Skip a value equal to the one before it in the same loop
            if i > start and nums[i] == nums[i - 1]:
                continue
            # 6. Add the value, extend from the next position, take the value out
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

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

Example 1, traced

Input
nums = [1,2,2]

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

Why it works

After sorting, one rule picks a single way to build each subset: take values from left to right, and from a group of equal values always take the leftmost ones. The loop only moves right, and the skip refuses a value whose equal left neighbor was on offer in the same place. So each different subset is built exactly once, and it is recorded when its call starts.

Time and space

Time O(n · 2^n), extra space O(n + output). One call runs per different subset, and n values have at most 2^n subsets. A call copies up to n values and loops over up to n positions: O(n · 2^n) time. The calls nest at most n + 1 deep and share one working subset: O(n + output) space.

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

• Sort before you skip. The skip compares only neighbors, so in [4, 0, 4] the two 4s never meet: [4] is recorded twice, and [4, 0] and [0, 4] both appear.
• Skip an equal value only in the loop that offered its twin. If every value equal to its left neighbor is skipped, two equal values never share a subset: [1, 2, 2] loses [2, 2] and [1, 2, 2].
• Record the subset at the start of every call, not only when no value is left. If you record only at the end, [1, 2, 2] returns [1, 2, 2] and [2, 2] and loses the other four subsets.

Pattern

Backtracking. Builds on 3Sum and Subsets.

Keep going