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: Sorted, the values are 1, 2, 3, and three values give 2^3 = 8 subsets. [1, 2] comes before [1, 2, 3] because it is its start, and [1, 2, 3] comes 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.

+13 hidden tests on Submit

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. A subset says yes or no to each position, and that is what the n bits of a number do. So the numbers from 0 to 2^n-1 are the subsets: for [1, 2, 3], the mask 5 is binary 101, bits 0 and 2 are set, and it stands for [1, 3]. Mask 0 is the empty subset and mask 7 is the full list.

Different masks give different subsets and every subset has a mask, so the loop produces all 2^n subsets exactly once. Reading the bits from position 0 upwards over sorted values writes each subset in ascending order.

The masks do not come out in the order the problem asks for. Mask 1 is [1], mask 2 is [2] and mask 3 is [1, 2], so [2] would land before [1, 2]. You fix that with a sort whose comparator goes value by value and puts a prefix first. The sort costs more than the generation: 2^n subsets need about n × 2^n comparisons, and each comparison reads up to n values. For n = 10 that is around 10^5 reads, still fast, but it is work the next approach 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. Below a node you may add any value that is larger than the last one you added. For sorted values [1, 2, 3] the root has the children [1], [2] and [3]; [1] has the children [1, 2] and [1, 3]; [1, 2] has the child [1, 2, 3]. Each subset sits in this tree exactly once, because there is only one way to write it in ascending order, and every node is an answer, not only the leaves.

Backtracking walks the tree with one shared list, path. To step down to a child you choose: append the value. You explore: recurse, and the helper records a copy of path the moment it arrives. Then you un-choose: remove the value, so path is back at the parent and the next sibling can be tried. Since every node is recorded on the way in, a parent is always written before its children.

That is why the output is in lexicographic order with no sort. The children of a node are tried from the smallest value up, and the walk finishes a whole branch before it starts the next one. For [1, 2, 3] it records [], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]: the order of a dictionary, with a prefix before its extensions.

The tree has 2^n nodes and copying a path costs up to n, so the time is O(n × 2^n), the size of the answer itself. Besides the output you keep one path and a call stack, both at most n deep.

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

Most wrong answers here come from the order or from sharing one list.

Appending path itself instead of a copy. Every entry then points at the same list, which is 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, and the walk is no longer in lexicographic order.
Recording only at the leaves, as you would for permutations. Every node of this tree is a subset; recording only paths that reach the end returns too few subsets.
Recursing on start+1 instead of i+1. A value can then follow a larger one or even itself, and you get lists such as [3, 2] and [3, 3] that are not subsets in ascending order.
Using the include or exclude tree (decide value 0, then value 1, and so on) and recording the leaves. It finds all 2^n subsets, but trying include first puts the full list first, and trying exclude first puts [3] before [2]. Neither is lexicographic.
A comparator that sorts by length first gives [], [1], [2], [3], [1, 2], which is a different order.

Frequently asked questions4

How many subsets does a set of n elements have?

2^n. Each element is either in or out, independently of the others, so the choices multiply: two for the first element, two for the second, and so on. 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 even returning the answer costs that much. Backtracking reaches this bound and keeps only O(n) extra space. Generating with bitmasks is as fast, but sorting the result afterwards adds another factor of n.

Should I use backtracking or bitmasks for Subsets?

Bitmasks are short, need no recursion and make the in or out choice visible as bits. Backtracking gives the subsets in lexicographic order by itself, and it adapts to the common variants: skipping repeated values, only subsets of size k, or only subsets that reach a target sum, where you can stop exploring a branch early.

How do you handle duplicate values in Subsets?

Sort the values, then in the loop of the backtracking helper skip a value that equals 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 sibling branch that starts with the second copy would only rebuild the same subsets.

Python

def subsets(nums):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

nums = [3, 1, 2]

Expected

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