Pattern visualizer

Subsets

The key insight: every subset of n elements is fully determined by n independent yes/no choices — include this element or don't — so exploring both branches at every index naturally enumerates all 2^n subsets exactly once, with no duplicates and nothing missed. Backtrack depth-first at each index: choose to EXCLUDE nums[i] first, recurse, then undo that and choose to INCLUDE it, recurse again — the push/pop on cur lets one array represent every path instead of allocating a new array per branch. The cells row shows the current partial subset (cur) as it's built; at each leaf (i === n) it's a complete subset. Animated on: nums = [1,2,3] — generate all 2^n = 8 subsets via an include/exclude decision tree.

Backtracking

step 1 / 14

line 5

i=0, cur=[]. Exclude nums[0]=1 — recurse to i=1 without adding it.

Pseudocode

1FUNCTION subsets(nums):
2  ans = empty list of subsets, cur = empty current subset
3  FUNCTION backtrack(i):
4    IF i === the length of nums:  add a copy of cur to ans, then RETURN
5    backtrack(i + 1)   (branch: EXCLUDE nums[i])
6    add nums[i] to the end of cur
7    backtrack(i + 1)   (branch: INCLUDE nums[i])
8    remove the last element of cur   (undo)
9  END FUNCTION
10  backtrack(0)
11  RETURN ans
12END FUNCTION

← / → step · space play · Home restart

Where to practice Backtracking

Practice Backtracking problems All Backtracking problems Back to roadmap