DSA Subsets

The problem

Subsets asks for every selection of a list of distinct values. A selection may take any of the values, in their original order. It may also take none of them.

The collection of all subsets of a set is called its power set. This article lists the results in include-first order. The full list prints first, and the empty subset prints last.

cases = [
    ([5], [[5], []]),
    ([1, 2], [[1, 2], [1], [2], []]),
    ([1, 2, 3], [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]),
    ([], [[]]),
]
for nums, expected in cases:
    print("nums", nums, "subsets:", expected)

Read the counts first. One value gives two subsets. Two values give four, and three values give eight. Even an empty list gives one subset, the empty one.

Intuition: each value is a yes-or-no choice

Each value faces one choice. The value joins the subset, or it stays out.

The choices multiply across values. Two values with two choices each give four subsets. A third value doubles the count again, to eight.

nums = [1, 2]
built = []
for take_first in (True, False):
    for take_second in (True, False):
        subset = []
        if take_first:
            subset.append(nums[0])
        if take_second:
            subset.append(nums[1])
        built.append(subset)
        print("1:", "in" if take_first else "out", "- 2:", "in" if take_second else "out", "->", subset)
print("subsets:", len(built))

Stopping at familiar sizes is the trap in this problem. Pairs and triples are only part of the answer. The empty subset and the full list are subsets too, and a size-by-size search must still cover every size from zero to n.

Brute force: read the choices off a counter

A bit is one binary digit, 0 or 1. The brute force turns each count from 0 up to 2^n minus 1 into a set of choices. The bits of the count say which values are in, with a set bit meaning in and a clear bit meaning out.

The test uses a shift. Shifting 1 left by i places makes a number with only bit i set. The test mask & (1 << i) keeps just that bit of the count. It passes exactly when value i belongs to the subset.

def subsets_brute(nums):
    results = []
    masks = 0
    bit_tests = 0
    for mask in range(2 ** len(nums)):
        masks += 1
        subset = []
        for i in range(len(nums)):
            bit_tests += 1
            if mask & (1 << i):
                subset.append(nums[i])
        results.append(subset)
    return results, masks, bit_tests

result, masks, bit_tests = subsets_brute([1, 2, 3])
for row in result:
    print(row)
print("masks read:", masks)
print("bit tests:", bit_tests)

The mask method works, but it rebuilds every subset from an empty list. It also scans all n bits of every mask, even the bits that stay clear. The bit test count shows that repeated scanning plainly.

The optimal solution: one shared path, one choice per value

The state is one shared path plus the index of the value now facing its choice, and the search appends the value, explores, then removes it before exploring the skip branch. That one sentence is the whole method.

A copy of the path is stored only when the index runs off the end of the list. At that moment the path holds one complete subset. Removing the value after the include branch is the backtrack step, and it leaves the path clean for the skip branch.

def subsets(nums):
    results = []
    path = []
    def search(index):
        if index == len(nums):
            results.append(list(path))
            return
        path.append(nums[index])
        search(index + 1)
        path.pop()
        search(index + 1)
    search(0)
    return results

cases = [
    ([5], [[5], []]),
    ([1, 2], [[1, 2], [1], [2], []]),
    ([1, 2, 3], [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]),
    ([], [[]]),
]
for nums, expected in cases:
    result = subsets(nums)
    print("nums", nums, "->", result, "match:", result == expected)

Every case matches. The search holds one partial subset at a time, instead of rebuilding each subset from a count. Each value is appended once and removed once along the way.

Walkthrough: [1, 2], one choice at a time

The walk follows the path through both choices for both values. A take line adds a value. A drop line removes it again, which is the backtrack step made visible.

nums = [1, 2]
path = []
results = []
def search(index):
    if index == len(nums):
        print("end of list - record", list(path))
        results.append(list(path))
        return
    path.append(nums[index])
    print("take", nums[index], "- path:", list(path))
    search(index + 1)
    path.pop()
    print("drop", nums[index], "- path:", list(path))
    search(index + 1)
search(0)
print("results:", results)

Read the records in order. They are [1, 2], [1], [2] and the empty subset. Each drop line undoes one choice so the other branch can run with a clean path.

Complexity

Time is O(n times 2^n) for n values. The answer itself is that large, because the values across all subsets total n times 2^(n-1), so no method that lists every subset can grow more slowly.

Extra space is O(n) besides the stored results. The shared path never holds more than one value per list position.

for n in [3, 4, 5]:
    print("values", n, "- subsets:", 2 ** n, "- values across all subsets:", n * 2 ** (n - 1))

Each added value doubles the subset count. The total size more than doubles, because the new value also joins half of the subsets that already existed.

Edge cases and pitfalls

The empty list has exactly one subset. It is the empty subset, reached by making no choices at all. A single value has two subsets, itself and the empty subset.

The method assumes distinct values. A repeated value faces its own choice like any other value, so repeated input produces repeated subsets. The last block shows that failure directly.

def subsets(nums):
    results = []
    path = []
    def search(index):
        if index == len(nums):
            results.append(list(path))
            return
        path.append(nums[index])
        search(index + 1)
        path.pop()
        search(index + 1)
    search(0)
    return results

print("empty list:", subsets([]))
print("one value:", subsets([9]))
print("four values, count:", len(subsets([1, 2, 3, 4])))
print("repeated value:", subsets([2, 2]))

The repeated row prints [2] twice, once per copy of the value. Handling repeated input needs a skip rule for equal neighbours, like the one the Permutations lesson uses for repeated values.