Difficulty: 🟡 Medium
Topics: Array, Backtracking, Bit Manipulation

Solution

LeetCode 78, Subsets

Problem Understanding

This problem asks us to generate every possible subset of a given array of unique integers. A subset is any selection of elements from the array, including the empty subset and the subset containing every element.

If the input array has n elements, then there are exactly 2^n possible subsets. This comes from the fact that each element has two choices: either it is included in a subset or it is not included.

For example, if the input is:

nums = [1,2,3]

then:

We can choose nothing: []
We can choose one element: [1], [2], [3]
We can choose two elements: [1,2], [1,3], [2,3]
We can choose all elements: [1,2,3]

Together, these form the complete power set.

The input consists of:

An integer array nums
Every element is unique
The array length is between 1 and 10

The output must contain all subsets, in any order.

The uniqueness guarantee is important because it means we do not need special duplicate handling logic. Problems like "Subsets II" require sorting and duplicate skipping, but this one does not.

The constraints are relatively small. Since nums.length <= 10, the maximum number of subsets is:

2^10 = 1024

This tells us that generating all subsets is feasible. In fact, any correct solution must output all subsets, so an exponential time complexity is unavoidable.

Important edge cases include:

A single-element array, such as [0]
Negative numbers
Generating the empty subset correctly
Ensuring subsets are copied properly during backtracking, otherwise mutations can corrupt results
Making sure every combination is generated exactly once

Approaches

Brute Force Approach

The brute force idea is to generate every possible combination manually by checking all inclusion and exclusion possibilities.

One way to do this is:

For every possible subset size from 0 to n
Generate all combinations of that size
Add them to the result

Another brute force interpretation is to iterate through every binary mask from 0 to 2^n - 1.

For example:

nums = [1,2,3]

000 -> []
001 -> [3]
010 -> [2]
011 -> [2,3]
100 -> [1]
101 -> [1,3]
110 -> [1,2]
111 -> [1,2,3]

Each bit determines whether an element is included.

This approach is correct because every subset corresponds to exactly one binary representation.

However, it still requires generating all 2^n subsets, and each subset may contain up to n elements. Therefore, the total complexity is exponential.

Optimal Approach

The optimal approach uses backtracking.

The key insight is that every element creates a branching decision:

Include the current element
Exclude the current element

By recursively exploring both choices, we naturally construct the full power set.

Backtracking is a natural fit because:

We build subsets incrementally
We can efficiently add and remove elements
The recursion tree directly represents all possible decisions

At each recursive call:

Add the current subset to the result
Try adding each remaining element
Recurse deeper
Remove the element to restore state

This generates all subsets without duplicates and without unnecessary work.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × 2^n)	O(n × 2^n)	Enumerates all binary masks or combinations
Optimal	O(n × 2^n)	O(n × 2^n)	Backtracking builds subsets incrementally

Although both approaches have the same asymptotic complexity, backtracking is cleaner, more flexible, and easier to extend to related problems.

Algorithm Walkthrough

Backtracking Algorithm

Create an empty result list to store all subsets.
Create a helper function called backtrack(start, current_subset).

start tells us where to continue searching.
current_subset stores the subset currently being built.

At the beginning of every recursive call, append a copy of current_subset to the result.

This works because every intermediate subset is itself a valid answer. 4. Iterate through indices from start to the end of the array.

For each index:

Add the current number to current_subset
Recursively continue searching from the next index
Remove the number afterward

The removal step is the "backtracking" operation.

It restores the subset to its previous state so the next recursive branch starts cleanly. 6. Continue until all recursive paths are explored. 7. Return the result list.

Why it works

The algorithm works because every recursive level represents a decision point about whether to include future elements. By exploring every valid continuation exactly once, the recursion tree covers all possible subsets.

The start index ensures that elements are only considered in forward order, preventing duplicate subsets such as both [1,2] and [2,1].

Python Solution

from typing import List

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

        def backtrack(start: int, current_subset: List[int]) -> None:
            result.append(current_subset[:])

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

        backtrack(0, [])
        return result

The implementation begins by creating the result list that will store all subsets.

The nested backtrack function handles recursive exploration. The start parameter ensures we only consider elements after the current position, preventing duplicates and preserving ordering.

At the beginning of every recursive call, we copy the current subset into the result. The copy is important because lists in Python are mutable. Without copying, later modifications would affect previously stored subsets.

Inside the loop, we add one element, recurse deeper, and then remove that element afterward. This allows the same list object to be reused efficiently across recursive calls.

Finally, the recursion begins with an empty subset and starting index 0.

Go Solution

func subsets(nums []int) [][]int {
    result := [][]int{}
    currentSubset := []int{}

    var backtrack func(start int)

    backtrack = func(start int) {
        subsetCopy := make([]int, len(currentSubset))
        copy(subsetCopy, currentSubset)

        result = append(result, subsetCopy)

        for i := start; i < len(nums); i++ {
            currentSubset = append(currentSubset, nums[i])

            backtrack(i + 1)

            currentSubset = currentSubset[:len(currentSubset)-1]
        }
    }

    backtrack(0)

    return result
}

The Go implementation follows the same recursive structure as the Python version.

One important difference is that slices in Go share underlying memory. Because of this, we must explicitly create a copy of currentSubset before appending it to result. If we appended the slice directly, later modifications would affect previously stored subsets.

The backtracking step removes the last element using slice truncation:

currentSubset = currentSubset[:len(currentSubset)-1]

Go does not require special handling for integer overflow here because the constraints are very small.

Worked Examples

Example 1

nums = [1,2,3]

Initial state:

Step	Current Subset	Result
Start	[]	[[]]

Recursive exploration:

Action	Current Subset	Result Added
Add 1	[1]	[1]
Add 2	[1,2]	[1,2]
Add 3	[1,2,3]	[1,2,3]
Backtrack 3	[1,2]	-
Backtrack 2	[1]	-
Add 3	[1,3]	[1,3]
Backtrack 3	[1]	-
Backtrack 1	[]	-
Add 2	[2]	[2]
Add 3	[2,3]	[2,3]
Backtrack 3	[2]	-
Backtrack 2	[]	-
Add 3	[3]	[3]
Backtrack 3	[]	-

Final result:

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

Example 2

nums = [0]

Initial call:

Step	Current Subset	Result
Start	[]	[[]]

Recursive process:

Action	Current Subset	Result Added
Add 0	[0]	[0]
Backtrack 0	[]	-

Final result:

[[], [0]]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × 2^n)	There are `2^n` subsets, and copying each subset takes up to `O(n)` time
Space	O(n × 2^n)	The output stores all subsets, each potentially length `n`

The dominant factor is the total number of subsets. Since every valid solution must output all subsets, exponential complexity is unavoidable.

The recursion stack itself only uses O(n) space, because the maximum recursion depth equals the number of elements.

Test Cases

from typing import List

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

        def backtrack(start: int, current_subset: List[int]) -> None:
            result.append(current_subset[:])

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

        backtrack(0, [])
        return result

solution = Solution()

# Example case with three elements
assert sorted(solution.subsets([1, 2, 3])) == sorted([
    [],
    [1],
    [2],
    [3],
    [1, 2],
    [1, 3],
    [2, 3],
    [1, 2, 3]
])

# Single element array
assert sorted(solution.subsets([0])) == sorted([
    [],
    [0]
])

# Two elements
assert sorted(solution.subsets([1, 2])) == sorted([
    [],
    [1],
    [2],
    [1, 2]
])

# Negative numbers
assert sorted(solution.subsets([-1, 1])) == sorted([
    [],
    [-1],
    [1],
    [-1, 1]
])

# Larger input size
result = solution.subsets([1, 2, 3, 4])

# Should contain 2^4 = 16 subsets
assert len(result) == 16

# Empty subset must exist
assert [] in result

# Full subset must exist
assert [1, 2, 3, 4] in result

Test Summary

Test	Why
`[1,2,3]`	Verifies standard multi-element behavior
`[0]`	Tests smallest valid input
`[1,2]`	Tests simple subset generation
`[-1,1]`	Ensures negative numbers work correctly
`[1,2,3,4]`	Verifies correct subset count and scaling

Edge Cases

Single Element Array

A single-element input such as [0] is the smallest valid case. The algorithm must still produce both the empty subset and the subset containing the element itself.

A common mistake is forgetting to include the empty subset. This implementation avoids that by appending the current subset at the start of every recursive call, including the initial empty state.

Negative Numbers

The problem allows values between -10 and 10, including negatives. Some incorrect implementations accidentally assume only positive integers.

This algorithm never performs arithmetic operations on the values themselves. It only stores and removes elements, so negative numbers behave identically to positive ones.

Proper Backtracking State Restoration

One of the most common bugs in recursive subset generation is failing to restore state after recursion.