Subsets

+10

You get a list nums of different integers. Return every subset of it, the empty one and the full list included, so n values give 2^n subsets. Write each subset with its values in ascending order, and list the subsets in lexicographic order: compare two subsets value by value, the first difference decides, and a subset that is the start of another comes before it. For [1, 2] the answer is [[], [1], [1, 2], [2]].

Function

subsets(nums: integer-array) → integer-2d-array

numsinteger-array: the values, all different, in any order
Returnsinteger-2d-array: every subset, each sorted ascending, listed in lexicographic order

Constraints

1 ≤ nums.length ≤ 10
-10 ≤ nums[i] ≤ 10
All values in nums are different.
nums may come in any order.

Examples

Input: nums = [3, 1, 2]
Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
Explanation: Three values give 2^3 = 8 subsets. [1, 2] comes before [1, 2, 3] because it is its start, and [1, 2, 3] before [1, 3] because 2 is smaller than 3 at the second position.

Input: nums = [0]
Output: [[], [0]]
Explanation: One value has two subsets: leave it out and get [], or take it and get [0]. The empty subset always comes first.

Input: nums = [5, -2]
Output: [[], [-2], [-2, 5], [5]]
Explanation: The values sort to -2 and 5, so [-2, 5] is written in that order. Every subset that holds -2 comes before [5], because -2 is smaller than 5.

Follow-up

Can you produce the same list without recursion, building each subset directly from the one before it?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

There are 2^n subsets, so no method does less than O(2^n) work. The real question is how to produce each subset once, in the required order, without sorting 1024 lists afterwards. Backtracking over the sorted values, recording every node of the decision tree as you enter it, walks the subsets in exactly lexicographic order.

Bitmasks, then sort

Intuition

Line the sorted values up at positions 0 to n-1. The n bits of a number say yes or no to each position, so the numbers 0 to 2^n-1 are the subsets, each exactly once: for [1, 2, 3], mask 5 is binary 101 and stands for [1, 3]. Reading the bits from position 0 up writes each subset in ascending order.

The masks come out in the wrong order: mask 2 is [2] and mask 3 is [1, 2], so [2] lands before [1, 2]. A sort that compares value by value and puts a prefix first fixes it. That sort costs about n × 2^n comparisons of up to n values each, around 10^5 reads at n = 10, work the backtracking never does.

Algorithm

Sort nums so every subset reads in ascending order.
For every mask from 0 to 2^n-1, collect the values at the positions whose bit is set.
Sort the list of subsets: at the first position where two differ, the smaller value wins, and if one runs out first, it comes first.
Return the sorted list.

def subsets(nums):
    values = sorted(nums)
    n = len(values)
    result = []
    for mask in range(1 << n):
        # Bit i of mask says whether values[i] is in this subset.
        result.append([values[i] for i in range(n) if (mask >> i) & 1])
    # Python compares lists position by position, and a prefix comes first.
    result.sort()
    return result

Backtracking: choose, explore, un-choose

Intuition

Picture the subsets as a tree. The root is the empty subset, and below a node you may add any value larger than its last one: for [1, 2, 3], [1] has the children [1, 2] and [1, 3]. Each subset appears once, because it has only one ascending spelling, and every node is an answer, the inner ones included.

Backtracking walks the tree with one shared list, path, and records a copy of it on arrival at every node. That puts each parent before its children, and trying children from the smallest value up finishes one branch before the next: lexicographic order with no sort.

The tree has 2^n nodes and each copy costs up to n: O(n × 2^n), the size of the answer, plus O(n) for the path and the call stack.

Algorithm

Sort the values.
Write explore(start). It first appends a copy of path to the result.
Then, for each index i from start to the end: append values[i] to path (choose), call explore(i+1) (explore), and remove the last value (un-choose).
Call explore(0) with an empty path and return the result.

def subsets(nums):
    values = sorted(nums)
    result = []
    path = []

    def explore(start):
        # Every node of the decision tree is a subset: record it on the way in.
        result.append(path[:])
        for i in range(start, len(values)):
            path.append(values[i])  # choose
            explore(i + 1)          # explore: only larger values may follow
            path.pop()              # un-choose

    explore(0)
    return result

Pitfalls and edge cases

Appending path itself instead of a copy. Every entry then points at one list, empty when the walk ends, so you return 2^n copies of [].
Forgetting to sort nums. With [3, 1, 2] the tree builds [3, 1], which is not ascending.
Recording only at the leaves, as for permutations. Every node is a subset, so you return too few.
Recursing on start+1 instead of i+1. A value can then follow a larger one or itself, giving lists such as [3, 2] and [1, 3, 3].
Recording the leaves of an include or exclude tree. It finds all 2^n subsets, but include first puts the full list first, and exclude first puts [3] before [2].

Frequently asked questions3

How many subsets does a set of n elements have?

2^n. Each element is in or out, independently of the others, so the choices multiply. Three values give 8 subsets and ten give 1024, counting the empty subset and the full set.

What is the time complexity of the Subsets problem?

O(n × 2^n). There are 2^n subsets and writing one out takes up to n steps, so returning the answer alone costs that much. Backtracking reaches this bound with O(n) extra space; bitmasks followed by a sort add another factor of n.

How do you handle duplicate values in Subsets?

Sort the values, then in the helper's loop skip a value equal to the one before it at the same level: i > start and values[i] == values[i-1]. The first copy already explores every subset that uses it, so a branch starting with the second copy would rebuild the same subsets.

def subsets(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [3, 1, 2]

Expected Output

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