LeetCode 78 · Medium · Backtracking

Subsets

Given an array nums of distinct integers, return every possible subset of it, the empty one included, with no subset listed twice. Any order is fine.

O(n · 2ⁿ)time
O(n)space besides the output
take / skipone decision per element

1–5 distinct integers from −10 to 10 · 5 values already grow a 63-node tree

nums blue = taken on this path · faded = skipped · i points at the next decision

subset the partial answer on the current path

decision tree one node per call · left edge takes nums[i], right edge skips it

res 0 subsets

List<List<Integer>> res = new ArrayList<>();List<Integer> subset = new ArrayList<>();int[] nums;public List<List<Integer>> subsets(int[] nums) { this.nums = nums; dfs(0); return res;}private void dfs(int i) { if (i >= nums.length) { res.add(new ArrayList<>(subset)); return; } subset.add(nums[i]); // take nums[i] dfs(i + 1); subset.remove(subset.size() - 1); // undo, then skip it dfs(i + 1);}
i
—
subset
[]
depth
0
res.size()
0

Why it works

  1. Brute force counts in binary. Each mask from 0 to 2ⁿ − 1 picks a subset by its set bits. That is also O(n · 2ⁿ), but it cannot prune, so it does not carry over to Combination Sum or N-Queens.
  2. Every element is one yes/no decision. Depth i of the tree decides nums[i]. A root-to-leaf path fixes all n decisions, so each leaf is a different subset and every subset is some leaf.
  3. 2ⁿ leaves, O(n) each. The tree has 2ⁿ leaves and 2ⁿ − 1 inner calls; copying a subset at a leaf costs up to n. The recursion and subset are at most n deep.
  4. Pitfall: append a copy. res.add(subset) stores the same List reference every time, and backtracking empties it, so res ends up full of empty lists. Use new ArrayList<>(subset).
  5. Undo before the other branch. subset.remove(subset.size() - 1) restores the state the parent had, so the skip branch starts clean. That add / recurse / remove rhythm is the whole backtracking template.
  6. Follow-up, Subsets II (90): with duplicate values, sort first and skip a whole run of equal values in the skip branch.