LeetCode 78: Subsets

Problem Restatement

We are given an integer array nums.

Every element in nums is unique.

We need to return all possible subsets of nums.

A subset may contain:

The answer must not contain duplicate subsets. The subsets may be returned in any order.

The official problem states that nums contains unique elements and asks for the full power set. The constraints are small: 1 <= nums.length <= 10, -10 <= nums[i] <= 10, and all numbers are unique.

Input and Output

Function shape:

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

Examples

Example 1:

nums = [1, 2, 3]

Each number has two choices:

1. Include it.
2. Exclude it.

The full answer is:

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

Example 2:

nums = [0]

There are only two subsets:

[
    [],
    [0],
]

First Thought: Binary Choice

For each number, we make a decision.

For example:

nums = [1, 2, 3]

At 1, choose:

take 1
skip 1

At 2, choose:

take 2
skip 2

At 3, choose:

take 3
skip 3

Since every element has two choices, the number of subsets is:

2^n

So any correct solution must produce 2^n results.

Key Insight

This problem is a natural backtracking problem.

We build one subset step by step.

At every index i, we decide whether nums[i] belongs to the current subset.

The recursive state is:

When i == len(nums), we have made a decision for every element, so path is one complete subset.

Algorithm

Start with:

ans = []
path = []

Define:

backtrack(i)

At each index i:

1. If i == len(nums), copy path into ans.
2. Otherwise, include nums[i], then recurse.
3. Undo the include choice.
4. Exclude nums[i], then recurse.

This directly models the two choices for each element.

Walkthrough

Use:

nums = [1, 2]

Start with:

path = []
i = 0

At i = 0, the current number is 1.

Take 1:

path = [1]

At i = 1, the current number is 2.

Take 2:

path = [1, 2]

Now all decisions are made, so record:

[1, 2]

Backtrack and skip 2:

path = [1]

Record:

[1]

Backtrack to the first decision and skip 1:

path = []

Then take 2:

path = [2]

Record:

[2]

Finally skip 2:

path = []

Record:

[]

The result contains every possible subset.

Correctness

At each index, the algorithm explores exactly two choices: include the current number or exclude it.

A subset of nums can be described by one such decision for every index. For example, with three numbers, one subset may correspond to:

include nums[0]
exclude nums[1]
include nums[2]

The recursion explores every sequence of such decisions. Therefore, every possible subset is eventually generated.

The algorithm records a subset only when i == len(nums). At that point, every element has already been either included or excluded, so the recorded path is a complete valid subset.

No duplicate subsets are generated because each subset corresponds to exactly one include-or-exclude decision sequence. Since nums contains unique elements, two different decision sequences cannot produce the same subset.

Therefore, the algorithm returns all valid subsets exactly once.

Complexity

Let:

n = len(nums)

There are 2^n subsets.

Copying each subset costs up to O(n).

Implementation

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

        def backtrack(i: int) -> None:
            if i == len(nums):
                ans.append(path.copy())
                return

            path.append(nums[i])
            backtrack(i + 1)
            path.pop()

            backtrack(i + 1)

        backtrack(0)
        return ans

Code Explanation

The result list stores all completed subsets:

ans = []

The current subset is stored in:

path = []

The recursive function receives the current index:

def backtrack(i: int) -> None:

When i reaches the end, every number has been considered:

if i == len(nums):
    ans.append(path.copy())
    return

We copy path because path is mutable. Without .copy(), all answers would refer to the same list object.

The first branch includes the current number:

path.append(nums[i])
backtrack(i + 1)
path.pop()

The pop() undoes the choice before we explore the second branch.

The second branch excludes the current number:

backtrack(i + 1)

Finally, we start from index 0:

backtrack(0)

Alternative Implementation: Growing Subsets

Another common backtracking style records the current path at every call.

Then it tries to add each later number.

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

        def backtrack(start: int) -> None:
            ans.append(path.copy())

            for i in range(start, len(nums)):
                path.append(nums[i])
                backtrack(i + 1)
                path.pop()

        backtrack(0)
        return ans

This version is often shorter.

It produces the same set of subsets, possibly in a different order.

Testing

Because LeetCode accepts any order, normalize the result before comparing.

def normalize(result):
    return sorted(tuple(sorted(row)) for row in result)

def run_tests():
    s = Solution()

    assert normalize(s.subsets([1, 2, 3])) == normalize([
        [],
        [1],
        [2],
        [1, 2],
        [3],
        [1, 3],
        [2, 3],
        [1, 2, 3],
    ])

    assert normalize(s.subsets([0])) == normalize([
        [],
        [0],
    ])

    assert normalize(s.subsets([1, 2])) == normalize([
        [],
        [1],
        [2],
        [1, 2],
    ])

    result = s.subsets([4, 5, 6, 7])
    assert len(result) == 16
    assert len(normalize(result)) == 16

    print("all tests passed")

run_tests()

Test meaning: