Backtracking

Subsets / Power Set

For each element, you have two choices: include it or skip it. This creates a binary decision tree with 2ⁿ leaves — each leaf is a unique subset. Recurse through elements, building the current subset as you go.

O(2^n)

O(n)

How It Works

Generating all subsets treats each element as an independent binary decision: include it or skip it. The recursion walks the array with an index and a growing current subset; at each index it branches twice — once after appending the element, once without it — and recurses to the next index. When the index passes the end, the current subset is one of the 2^n leaves of this decision tree and gets recorded. An equivalent formulation adds the current partial subset to the results at every call and loops over remaining elements from a start index.

The output itself has 2^n subsets averaging n/2 elements, so O(n * 2^n) total work is inherent, not a flaw of the method. The choose-recurse-unchoose discipline — append, recurse, pop — keeps a single mutable buffer valid across branches, using only O(n) auxiliary space beyond the output. Sorting first and skipping adjacent duplicates extends the same skeleton to inputs with repeated values.

Step-by-Step Visualization

Generate all subsets of [1,2,3]

Start[] (empty)

1/3

Code

Java

static List<List<Integer>> subsets(int[] nums) {
  List<List<Integer>> result = new ArrayList<>();
  backtrack(nums, 0, new ArrayList<>(), result);
  return result;
}

static void backtrack(int[] nums, int start, List<Integer> current, List<List<Integer>> result) {
  result.add(new ArrayList<>(current));
  for (int i = start; i < nums.length; i++) {
    current.add(nums[i]);
    backtrack(nums, i + 1, current, result);
    current.remove(current.size() - 1);
  }
}

Tips & Gotchas

1For each element: include it or skip it (two choices)

2Backtrack after including to explore the skip path

3Creates a binary decision tree

Practice Problems

1Subsets
2Subsets II
3Letter Case Permutation
4Combination Sum
5Palindrome Partitioning

About the Backtracking Pattern

Systematically explore all possible solutions by making choices one at a time. If a choice leads to a dead end, undo it (backtrack) and try the next option. Think of it as exploring a decision tree — you go deep, and come back up when stuck.

Key insight

Every recursive solution has: base case, recursive case, and combining step. For backtracking, add: make choice → recurse → undo choice. Prune early to avoid TLE.

Common Recursion Interview Problems

Subsets
Permutations
Combination Sum
N-Queens
Word Search
Generate Parentheses
Letter Combinations of Phone Number

Frequently Asked Questions

Why do I need to copy the current subset before adding it to the results?

The recursion mutates one shared buffer via push and pop, so storing a reference to it means every stored 'subset' later reflects the same final state. Snapshot it — copy the list — at the moment you record it, so each result is frozen.

How are duplicate elements prevented from producing duplicate subsets?

Sort the input first, then at each level of recursion skip an element if it equals the previous element at the same level (i > start and nums[i] == nums[i-1]). This ensures each multiset of values is generated exactly once, without needing a dedupe hash set.

Is there a non-recursive way to enumerate subsets?

Yes — iterate a counter from 0 to 2^n - 1 and treat each bit as the include/skip decision for one element. Bitmask enumeration is compact and cache-friendly for n up to about 20, though the recursive form generalizes more easily to pruning and duplicate handling.