Subsets [Medium] — Power Set via Backtracking, Bit Manipulation & Cascading [LC 78]

Problem Statement#

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input:  nums = [1, 2, 3]
Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

Example 2:

Input:  nums = [0]
Output: [[], [0]]

Constraints:

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• All the numbers of nums are unique

Why This Problem Matters#

LC 78 — Subsets is not just a medium-difficulty warm-up. It is arguably the single most important combinatorics problem you will encounter in a technical interview. Here is why.

Every problem that asks you to "enumerate all possible X" — combinations, permutations, partitions, paths through a decision tree — uses the same fundamental machinery that Subsets teaches you. Once you internalize how to build the subset decision tree, you unlock:

• LC 90 — Subsets II (same problem with duplicates)
• LC 39 — Combination Sum (subsets with a target constraint)
• LC 46 — Permutations (order matters, no repeated elements)
• LC 131 — Palindrome Partitioning (subset-style partition choices)
• LC 17 — Letter Combinations of a Phone Number

FAANG interviewers specifically use LC 78 as a backtracking competency test. The problem is clean enough that you can solve it multiple ways, and interviewers often ask: "Can you show me another approach?" Having all three methods ready — backtracking, bit manipulation, and iterative cascading — signals that you understand the deeper structure of the problem, not just a memorized pattern.

There is also a subtle difficulty hiding in plain sight: managing mutable state correctly. Beginners frequently submit solutions that produce all empty lists, or lists that are all references to the same object. Getting the deep copy right, and understanding why it is necessary, is itself a common interview discussion point.

The bottom line: do not treat this as a throwaway problem. LC 78 is the foundation of an entire family of interview questions. Solve it three ways, internalize the decision tree mental model, and every downstream combinatorics problem becomes dramatically easier.

The Core Insight#

Before writing a single line of code, you need to understand the core decision that drives every approach.

For each element in the array, you face a binary choice: include it or exclude it. That's it. Every subset is just a sequence of these binary decisions made for each element in order.

For nums = [1, 2, 3], the decision tree looks like this:

                         []
                /                 \
           [1]                     []
          /    \                /       \
      [1,2]    [1]          [2]          []
      /  \     /  \         /  \        /  \
 [1,2,3][1,2][1,3][1]  [2,3][2] [3]   []

Every leaf node is a valid subset. There are 2^n leaves for n elements — 2^3 = 8 for our example. This decision-tree structure is the mental model that unifies all three approaches.

Approach 1: Backtracking (Depth-First Search)#

Backtracking is the most general approach and the one interviewers most want to see. You walk the decision tree depth-first. At each node, you record the current state as a valid subset, then try extending it by adding each remaining element one at a time.

The crucial mechanism is the start index. By only considering elements at index start or later, you ensure you never go backwards in the array — this automatically prevents duplicate subsets like [2, 1] when [1, 2] already exists.

The undo step (path.pop() in Python, cur.pop() in JavaScript) is what makes it "backtracking" — you restore the state after exploring a branch so the parent node can try the next option.

Approach 2: Bit Manipulation (Bitmask Enumeration)#

For n elements, there are exactly 2^n subsets. If you enumerate every integer from 0 to 2^n - 1, each integer's binary representation corresponds to exactly one subset. Bit j being 1 means "include element at index j."

For nums = [1, 2, 3] with n = 3:

This approach is elegant, iterative, and completely avoids recursion. The trade-off: it only works when n is small enough that 2^n fits in memory (which the constraints guarantee here, with n <= 10).

Approach 3: Iterative Cascading#

This approach builds the answer incrementally. You start with just the empty set. For each new element, you take every existing subset in the result, make a copy of it with the new element appended, and add those new subsets to the result.

Start:       [[]]
Add 1:       [[], [1]]
Add 2:       [[], [1], [2], [1,2]]
Add 3:       [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

At each step, the result doubles in size — which is exactly right since adding one element doubles the number of subsets.

Visual Dry Run#

Let's trace the backtracking approach in full detail on nums = [1, 2, 3].

We call dfs(start=0, path=[]).

Step 1: start=0, path=[] Record [] into result. Result: [[]] Try i=0: append 1 → path=[1], call dfs(1, [1])

Step 2: start=1, path=[1] Record [1] into result. Result: [[], [1]] Try i=1: append 2 → path=[1,2], call dfs(2, [1,2])

Step 3: start=2, path=[1,2] Record [1,2]. Result: [[], [1], [1,2]] Try i=2: append 3 → path=[1,2,3], call dfs(3, [1,2,3])

Step 4: start=3, path=[1,2,3] Record [1,2,3]. Result: [[], [1], [1,2], [1,2,3]] start == len(nums), no more elements to try. Return.

Backtrack to Step 3: pop 3 → path=[1,2]. No more i to try. Return.

Backtrack to Step 2: pop 2 → path=[1]. Try i=2: append 3 → path=[1,3], call dfs(3, [1,3])

Step 5: start=3, path=[1,3] Record [1,3]. Result: [[], [1], [1,2], [1,2,3], [1,3]] Return.

Backtrack to Step 2: pop 3 → path=[1]. No more i. Return.

Backtrack to Step 1: pop 1 → path=[]. Try i=1: append 2 → path=[2], call dfs(2, [2])

Step 6: start=2, path=[2] Record [2]. Try i=2: append 3 → path=[2,3], call dfs(3, [2,3])

Step 7: start=3, path=[2,3] Record [2,3]. Return.

Backtrack to Step 6: pop 3 → path=[2]. Return.

Backtrack to Step 1: pop 2 → path=[]. Try i=2: append 3 → path=[3], call dfs(3, [3])

Step 8: start=3, path=[3] Record [3]. Return.

Backtrack to Step 1: pop 3 → path=[]. No more i. Return.

Final result: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

All 8 subsets correctly enumerated.

Common Mistakes#

Mistake 1: Appending the path object directly instead of a copy#

This is the single most common bug. In Python, lists are passed by reference. If you write res.append(path) instead of res.append(path[:]), every entry in res points to the same list object. As you mutate path during backtracking, all previously recorded subsets change alongside it. By the end, every entry in res will be an empty list [].

Always snapshot the current state: res.append(path[:]) in Python or res.push([...cur]) in JavaScript.

Mistake 2: Not using a start index, leading to duplicates#

If you iterate from index 0 on every recursive call instead of from start, you will revisit earlier elements and produce duplicate subsets. For example, without a start index, after recording [1] and recursing, you might later record [2] and recurse back to add 1, producing [2, 1] — a duplicate of [1, 2] in a different order.

The start parameter is not optional — it is the mechanism that enforces forward-only traversal through the array.

Mistake 3: Forgetting the base case adds the current path, not just leaves#

In many tree problems, you only record a value at leaf nodes. In Subsets, every node in the decision tree is a valid subset, including intermediate nodes. This means you should record path[:] at the very beginning of each dfs call, before any recursive branching — not just when start == len(nums).

Beginners who write the base case as if start == len(nums): res.append(path[:]) will only collect complete subsets of maximum length, missing all the shorter ones.

Mistake 4: Off-by-one in bitmask enumeration#

When using the bitmask approach, you iterate from 0 to 2^n - 1 inclusive. The range should be range(1 << n), which goes from 0 to (1 << n) - 1. Writing range(1, 1 << n) skips the empty subset [] corresponding to mask 0.

Mistake 5: Mutating the input array#

Some candidates sort nums before running the algorithm. For LC 78, all elements are distinct and you can return subsets in any order, so sorting is unnecessary. More importantly, modifying the input is considered bad practice in interviews — always ask whether you are allowed to mutate the input, and if not, work on a copy.

Solutions#

Python — Backtracking#

def subsets(nums: list[int]) -> list[list[int]]:
    result = []  # will hold all discovered subsets
 
    def dfs(start: int, path: list[int]) -> None:
        # Record a snapshot of the current path as a valid subset.
        # We do this at EVERY call, not just at leaves — every node is a valid subset.
        result.append(path[:])  # path[:] creates a shallow copy; critical to avoid reference bugs
 
        # Try adding each element at index i or beyond (never go backwards)
        for i in range(start, len(nums)):
            path.append(nums[i])   # Choose: include nums[i] in the current subset
            dfs(i + 1, path)       # Explore: recurse with the next available index
            path.pop()             # Un-choose: backtrack by removing nums[i]
 
    dfs(0, [])   # Start DFS from index 0 with an empty path
    return result

Python — Bit Manipulation#

def subsets_bitmask(nums: list[int]) -> list[list[int]]:
    n = len(nums)          # number of elements; subsets count = 2^n
    result = []
 
    # Enumerate every integer from 0 to 2^n - 1.
    # Each integer represents one unique subset via its binary digits.
    for mask in range(1 << n):  # 1 << n equals 2^n
        subset = []
        for j in range(n):
            # Check if bit j is set in this mask.
            # If set, include nums[j] in this subset.
            if mask & (1 << j):
                subset.append(nums[j])
        result.append(subset)
 
    return result

Python — Iterative Cascading#

def subsets_cascading(nums: list[int]) -> list[list[int]]:
    result = [[]]   # Start with just the empty subset
 
    for num in nums:
        # For every existing subset, create a new subset that also contains num.
        # We must snapshot result's current length before the loop;
        # otherwise we'd keep extending newly added subsets in the same pass.
        new_subsets = [existing + [num] for existing in result]
        result.extend(new_subsets)   # Append the new subsets to the result
 
    return result

JavaScript — Backtracking#

var subsets = function(nums) {
    const result = [];  // accumulates all discovered subsets
 
    function dfs(start, cur) {
        // Snapshot the current array as a valid subset.
        // Spread syntax [...cur] creates a shallow copy — essential here.
        result.push([...cur]);
 
        // Extend the current subset by picking any element at index >= start
        for (let i = start; i < nums.length; i++) {
            cur.push(nums[i]);    // Choose: add nums[i] to current subset
            dfs(i + 1, cur);     // Explore: recurse with elements to the right only
            cur.pop();           // Un-choose: remove nums[i] to try other branches
        }
    }
 
    dfs(0, []);   // kick off DFS with an empty working array
    return result;
};

JavaScript — Bit Manipulation#

var subsets_bitmask = function(nums) {
    const n = nums.length;
    const result = [];
 
    // Enumerate all integers from 0 to 2^n - 1.
    // Each integer encodes one subset via its binary representation.
    for (let mask = 0; mask < (1 << n); mask++) {
        const subset = [];
        for (let j = 0; j < n; j++) {
            // If bit j is set in mask, include nums[j] in this subset
            if (mask & (1 << j)) {
                subset.push(nums[j]);
            }
        }
        result.push(subset);
    }
 
    return result;
};

JavaScript — Iterative Cascading#

var subsets_cascading = function(nums) {
    let result = [[]];   // begin with just the empty subset
 
    for (const num of nums) {
        // For every currently known subset, add a new version that includes num.
        // map over the current result (before it grows) to avoid infinite loop.
        const newSubsets = result.map(existing => [...existing, num]);
        result = result.concat(newSubsets);  // double the result size
    }
 
    return result;
};

Complexity Analysis#

Why O(n * 2^n)? There are exactly 2^n subsets. For each subset, we spend O(n) time to copy it into the output (the inner loop over bits, or the path[:] copy). The total work is therefore n * 2^n.

Space note: If we exclude the output array (which must be O(n * 2^n) no matter what), the backtracking approach uses O(n) extra space for the call stack (maximum recursion depth equals n). The bitmask and cascading approaches use O(1) extra space beyond the output.

In interviews, report the space as O(n * 2^n) including output or O(n) auxiliary for backtracking.

Follow-up Questions#

LC 90 — Subsets II (Subsets with Duplicates)#

This is the most immediate follow-up an interviewer will ask. The input array may now contain duplicates, and the output must not contain duplicate subsets.

The key change: sort the array first, then skip over duplicate elements at the same recursion level. When you are about to pick index i and nums[i] == nums[i-1] and i > start, skip — you have already explored this value's branch from this position.

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()   # Sort so duplicates are adjacent
    result = []
 
    def dfs(start: int, path: list[int]) -> None:
        result.append(path[:])
        for i in range(start, len(nums)):
            # Skip duplicates at the same decision level.
            # i > start means we're not looking at the first element at this level.
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            dfs(i + 1, path)
            path.pop()
 
    dfs(0, [])
    return result

The critical condition is i > start (not i > 0). Using i > 0 would incorrectly skip elements that happen to equal the previous level's element, generating too few subsets.

LC 39 — Combination Sum#

Here, you must find all subsets of candidates (with repetition allowed) that sum to target. The backtracking structure is identical to LC 78, but with two changes:

1. You may reuse the same element, so the recursive call passes i (not i + 1) as the new start.
2. You only record a subset when remaining == 0 (not at every node).

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
 
    def dfs(start: int, path: list[int], remaining: int) -> None:
        if remaining == 0:
            result.append(path[:])   # Found a valid combination
            return
        if remaining < 0:
            return   # Pruning: exceeded target, no need to continue
 
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            dfs(i, path, remaining - candidates[i])  # i, not i+1: reuse allowed
            path.pop()
 
    dfs(0, [], target)
    return result

Understanding that LC 78 and LC 39 share the same skeleton — and that the only difference is the "record" condition and whether you pass i or i+1 — is the mark of a candidate who truly understands backtracking.

This Pattern Solves#

The decision-tree / backtracking pattern from LC 78 directly applies to:

• LC 90 — Subsets II: add a duplicate-skip guard after sorting
• LC 39 — Combination Sum: allow element reuse; record only at remaining == 0
• LC 40 — Combination Sum II: no reuse, but input has duplicates; combine LC 78 + LC 90 logic
• LC 46 — Permutations: no start index; use a visited set to prevent reuse
• LC 47 — Permutations II: permutations with duplicates; sort + skip guard
• LC 77 — Combinations: pick exactly k elements; add a size check before recording
• LC 131 — Palindrome Partitioning: at each position, try every valid palindrome prefix as the "choice"
• LC 784 — Letter Case Permutation: at each character, branch on lowercase vs uppercase

Every one of these problems is a variation on the same theme: walk a decision tree, record valid states, backtrack to explore other branches.

Key Takeaways#

• LeetCode 78 — Subsets is a Medium asked at Amazon, Google, and Meta; it is the foundational problem for all backtracking subset/combination problems.
• Three approaches: backtracking O(n * 2^n), cascading/iterative O(n * 2^n), bit manipulation O(n * 2^n) — all optimal, backtracking is most versatile.
• Four backtracking steps: choose (add element), explore (recurse), un-choose (remove element), snapshot (append path[:] not path).
• The start index enforces left-to-right ordering of choices — this structural constraint prevents duplicate subsets without any deduplication logic.
• Total subsets: 2^n — every element is either included or excluded from each subset.
• Bit manipulation shortcut: iterate mask from 0 to 2^n - 1; include nums[i] when bit i is set in mask — elegant but harder to generalize.
• Escalates to LC 90 (Subsets II with duplicates): sort first, then skip nums[i] == nums[i-1] when i > start in the loop — same skeleton, one guard added.

The bitmask approach offers a clean alternative when n is small: each of the 2^n integers from 0 to 2^n - 1 is a unique bit-vector that perfectly describes one subset. The cascading approach offers the most intuitive explanation of why there are 2^n subsets: each new element exactly doubles the count.

Master all three. An interviewer asking "show me another way" is giving you a gift — take it.