Subsets: three ways to build a power set

The first time I solved this problem I went straight for bit manipulation. Compact, clever, done in ten minutes. Then a teammate asked me to walk through the logic live, and I had to draw three scratch diagrams before it clicked for him. The backtracking version, which I initially dismissed as "more code," turned out to be the one that generalizes to every other combination/permutation problem in the series. I keep that lesson around.

LeetCode 78 asks: given an array of unique integers, return all possible subsets. The output is the power set — every possible selection, including the empty one, including the full array.

What the constraints actually tell you

1 <= nums.length <= 10. Ten elements. That number is doing real work here.

A power set of n elements has 2^n subsets. At n=10, that's 1024 subsets. Even at O(n * 2^n) — which all three approaches hit — you're doing at most 10,240 operations. Nothing clever needed to stay under time. The constraint isn't tightening; it's giving you permission. Any algorithm that produces all subsets correctly is fast enough, so the choice between approaches comes down to readability and how far it generalizes, not raw performance.

All elements are unique. No deduplication logic needed. If there were duplicates you'd need extra work (that's LeetCode 90, Subsets II). Here, every distinct selection of indices produces a distinct subset.

Values range from -10 to 10. This doesn't affect the algorithm at all — negative numbers work fine through all three approaches.

Bit manipulation: every integer is a mask

Each subset of n elements can be represented as an n-bit number. Bit j being set means nums[j] is included. The integer 0 (all bits zero) is the empty subset. The integer 2^n - 1 (all bits set) is the full array. Iterating from 0 to 2^n - 1 and extracting the corresponding elements gives you every subset exactly once.

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        n = len(nums)
        result = []
        for mask in range(1 << n):  # 0 to 2^n - 1
            subset = []
            for j in range(n):
                if mask & (1 << j):
                    subset.append(nums[j])
            result.append(subset)
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        int n = nums.Length;
        var result = new List<IList<int>>();
        int total = 1 << n;
        for (int mask = 0; mask < total; mask++) {
            var subset = new List<int>();
            for (int j = 0; j < n; j++) {
                if ((mask & (1 << j)) != 0)
                    subset.Add(nums[j]);
            }
            result.Add(subset);
        }
        return result;
    }
}

For nums = [1, 2, 3]:

• mask = 0 (000) -> []
• mask = 1 (001) -> [1]
• mask = 2 (010) -> [2]
• mask = 3 (011) -> [1, 2]
• mask = 4 (100) -> [3]
• mask = 5 (101) -> [1, 3]
• mask = 6 (110) -> [2, 3]
• mask = 7 (111) -> [1, 2, 3]

Exactly the eight expected subsets.

Time: O(n _ 2^n) — 2^n masks, each requiring an n-bit scan. Space: O(n _ 2^n) for the output. The stack is constant depth; the only allocation is the result.

I'd use this approach if I needed a one-liner in a scripting context and knew the reader was comfortable with bitwise ops. In production code or an interview setting where you're asked to extend the solution, I wouldn't reach for it — the connection to "choose/skip" logic is non-obvious and doesn't generalize cleanly when you need to add constraints like "subsets that sum to k."

Backtracking: the include/exclude decision tree

At each element, you make a binary decision: include it in the current subset, or skip it. Recurse on both choices. When you've made a decision for every element, the current subset is complete — record a copy of it.

The recursion tree for [1, 2, 3] looks like this:

Eight leaves, eight subsets. Each leaf is reached after exactly n decisions.

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result = []
        current = []
 
        def backtrack(index: int) -> None:
            if index == len(nums):
                result.append(current[:])  # copy — not a reference
                return
            # skip nums[index]
            backtrack(index + 1)
            # take nums[index]
            current.append(nums[index])
            backtrack(index + 1)
            current.pop()  # undo — backtrack
 
        backtrack(0)
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>>();
        var current = new List<int>();
 
        void Backtrack(int index) {
            if (index == nums.Length) {
                result.Add(new List<int>(current));  // copy
                return;
            }
            // skip nums[index]
            Backtrack(index + 1);
            // take nums[index]
            current.Add(nums[index]);
            Backtrack(index + 1);
            current.RemoveAt(current.Count - 1);  // undo
        }
 
        Backtrack(0);
        return result;
    }
}

The by-hand trace for [1, 2, 3]:

backtrack(0)
  skip 1 → backtrack(1)
    skip 2 → backtrack(2)
      skip 3 → backtrack(3)  →  record []
      take 3 → backtrack(3)  →  record [3],  pop 3
    take 2 → backtrack(2)
      skip 3 → backtrack(3)  →  record [2]
      take 3 → backtrack(3)  →  record [2,3],  pop 3
      pop 2
  take 1 → backtrack(1)
    skip 2 → backtrack(2)
      skip 3 → backtrack(3)  →  record [1]
      take 3 → backtrack(3)  →  record [1,3],  pop 3
    take 2 → backtrack(2)
      skip 3 → backtrack(3)  →  record [1,2]
      take 3 → backtrack(3)  →  record [1,2,3],  pop 3
      pop 2
    pop 1

Every pop() in the trace is the backtrack step — it undoes the append from the take branch so the next call starts with a clean current. The current[:] copy at the leaf is non-negotiable: without it you'd be appending the same list object eight times, and all eight entries in result would point to whatever current ends up as after the final backtrack.

Time: O(n _ 2^n). Space: O(n _ 2^n) for output plus O(n) recursion stack depth — total dominated by output.

This is the approach I'd ship and the one worth memorizing. The include/exclude pattern maps directly onto Subsets II (add a sort + skip-duplicates guard), Combination Sum (add a "remaining target" parameter), and Permutations (swap include/exclude for position assignment). Once you own the backtracking skeleton, the variants are just one or two lines different.

Iterative expansion

Start with the empty subset. Process each element one at a time: for every existing subset in the result, create a new subset that is that existing subset plus the current element. Add those new subsets to the result. Repeat.

After processing 1: [[], [1]]
After processing 2: [[], [1], [2], [1,2]]
After processing 3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]

class Solution:
    def subsets(self, nums: list[int]) -> list[list[int]]:
        result: list[list[int]] = [[]]
        for num in nums:
            new_subsets = [subset + [num] for subset in result]
            result.extend(new_subsets)
        return result

public class Solution {
    public IList<IList<int>> Subsets(int[] nums) {
        var result = new List<IList<int>> { new List<int>() };
        foreach (int num in nums) {
            int count = result.Count;
            for (int i = 0; i < count; i++) {
                var newSubset = new List<int>(result[i]) { num };
                result.Add(newSubset);
            }
        }
        return result;
    }
}

Time: O(n _ 2^n). Space: O(n _ 2^n). Same asymptotic cost as the others. No recursion, so no stack depth concern — though at n=10 the stack from backtracking is 10 frames deep, which is completely harmless.

The iterative version is the easiest to convince yourself is correct: you can literally watch the result grow. But it doesn't generalize the way backtracking does. Adding a constraint like "only subsets of size k" requires filtering after the fact rather than pruning the search early. For this problem that's fine — n=10, you can afford the extra work. For larger or constrained variants, iterative expansion becomes awkward.

Edge cases

Single element (nums = [0]): all three approaches produce [[], [0]] correctly. The bit mask approach runs mask=0 (empty) and mask=1 (take index 0). Backtracking makes two calls at depth 0: skip produces [], take produces [0]. Iterative starts with [[]] and adds [[0]].

Maximum n=10: 1024 subsets, each up to 10 elements long. Python and C# both handle this without issue. The result list itself is the only nontrivial allocation — about 10KB of lists in the worst case.

Negative values (nums = [-1, 0, 1]): nothing in any approach assumes non-negative values. The bit mask indexing is by position, not value. Backtracking appends whatever nums[index] is. Iterative concatenates whatever num is. All three work unchanged.

All elements at their extreme values: nums can contain any integers from -10 to 10. The constraint guarantees all elements are distinct, so no deduplication concern even at the boundaries.

Comparison

All three have identical asymptotic complexity because the output itself is O(n * 2^n) — you can't do better when you're required to produce every subset. The constant factors differ a bit: iterative expansion allocates intermediate lists during the extend step, while backtracking reuses a single current list. In practice at n=10, this is completely irrelevant.

The real differentiator is how far each pattern travels. Backtracking is the one to know.

Where this sits in the backtracking series

Subsets is the cleanest entry point into backtracking because the include/exclude structure is binary and unconditional — no pruning, no constraints, just two choices per element. That makes it the right first problem in this series.

From here the natural progression is:

• Subsets II (LeetCode 90): same structure but the array may have duplicates. Add a sort, then skip over consecutive equal elements at the same recursion depth to avoid duplicate subsets. One extra guard in the backtrack function.
• Combinations (LeetCode 77): generate all subsets of exactly size k. Add a size check to the base case; prune branches early when len(current) + remaining_elements < k.
• Combination Sum (LeetCode 39): find all subsets that sum to a target. Add a running sum parameter; prune when the sum exceeds the target. Elements can be reused, so the recursive call doesn't advance the index.
• Permutations (LeetCode 46): instead of include/exclude by index, assign positions. Each recursive call picks an unused element for the current position. The include/exclude mental model shifts to a "used" boolean array or an in-place swap.

The skeleton stays the same across all of them: a current state, a recursive call that extends it, and a undo/backtrack step. Subsets is where you internalize that skeleton before the constraints complicate things.