78. Subsets

Reformulated question¶

Return every subset of a list of unique integers.

Compact example:

nums = [1, 2]
subsets = [[], [1], [2], [1, 2]]

Key trick¶

Build subsets incrementally:

start with [[]]
for each number, copy every existing subset and append that number

This doubles the number of subsets each step, which matches the power set.

Trap¶

Common mistakes:

forgetting the empty subset
mutating the same list object instead of creating a new subset
trying to deduplicate even though input is already unique
expecting better than \(O(n \cdot 2^n)\), which is impossible because output size is that large

Why this question is interesting¶

It is a clean test of:

recognizing power set structure
choosing between backtracking and iterative construction
understanding output-driven complexity

Solution with idiomatic Python¶

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        # Start with the empty subset.
        result = [[]]

        # For each number, add it to every existing subset.
        # This creates all subsets that include the current number.
        for num in nums:
            result += [subset + [num] for subset in result]

        return result

Alternative backtracking version:

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = []
        path = []

        def dfs(i: int) -> None:
            # One complete subset.
            if i == len(nums):
                result.append(path[:])
                return

            # Skip nums[i].
            dfs(i + 1)

            # Take nums[i].
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

        dfs(0)
        return result

Complexity:

time: \(O(n \cdot 2^n)\)
space: \(O(n \cdot 2^n)\) including output

Pytest test¶

import pytest


def normalize(result):
    return sorted(sorted(subset) for subset in result)


@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1, 2, 3], [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]),
        ([0], [[], [0]]),
        ([1, 2], [[], [1], [2], [1, 2]]),
        ([-1, 1], [[], [-1], [1], [-1, 1]]),
        ([4, 5, 6, 7], [
            [],
            [4], [5], [6], [7],
            [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7],
            [4, 5, 6], [4, 5, 7], [4, 6, 7], [5, 6, 7],
            [4, 5, 6, 7],
        ]),
    ],
)
def test_subsets(nums, expected):
    result = Solution().subsets(nums)
    assert normalize(result) == normalize(expected)
    assert len(result) == 2 ** len(nums)

Comment my solution¶

No solution provided.

## Solution
# Written after reading AI comments on the problem
class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = [[]]

        for x in nums:
            result += [part + [x] for part in result]
        return result