78. Subsets

Problem¶

Return every subset of a list of unique integers.

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 is it interesting?¶

It is a clean test of:

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

Python solution¶

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

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

        return res

    def subsets_2(self, nums: list[int]) -> list[list[int]]:
        res = []
        path = []

        def dfs(i):
            # One complete subset.
            if i == len(nums):
                res.append(path[:])
                return

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

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

        dfs(0)
        return res

Complexity:

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

Comment on my solution¶

Not 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