DSA Tracker

Visualize

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.

Details

Animated on: nums = [1,2,3] — generate all 2^n = 8 subsets via an include/exclude decision tree

Problem:SubsetsMedium

Pattern:Backtracking Basics

Backtracking

step 1 / 14

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

Every step in words

Show all 14 steps
  1. i=0, cur=[]. Exclude nums[0]=1 — recurse to i=1 without adding it.
  2. i=1, cur=[]. Exclude nums[1]=2 — recurse to i=2.
  3. i=2, cur=[]. Exclude nums[2]=3 — recurse to i=3=n. Leaf! Record cur=[]. ans=[[]].
  4. Back at i=2: now try INCLUDE. cur.push(3) → cur=[3]. Recurse to i=3=n. Leaf! Record [3]. ans=[[], [3]].
  5. Backtrack: cur.pop() removes 3. Back at i=1: now try INCLUDE nums[1]=2. cur.push(2) → cur=[2]. Recurse to i=2.
  6. i=2, cur=[2]. Exclude nums[2]=3 — recurse to i=3=n. Leaf! Record [2]. ans=[[], [3], [2]].
  7. Back at i=2: INCLUDE nums[2]=3. cur.push(3) → cur=[2,3]. Recurse to i=3=n. Leaf! Record [2,3]. ans=[[], [3], [2], [2,3]].
  8. Backtrack all the way to i=0: cur empties. Now try INCLUDE nums[0]=1. cur.push(1) → cur=[1]. Recurse to i=1.
  9. i=1, cur=[1]. Exclude nums[1]=2 — recurse to i=2.
  10. i=2, cur=[1]. Exclude nums[2]=3 — recurse to i=3=n. Leaf! Record [1]. ans=[[], [3], [2], [2,3], [1]].
  11. Back at i=2: INCLUDE nums[2]=3. cur.push(3) → cur=[1,3]. Recurse to i=3=n. Leaf! Record [1,3]. ans=[[], [3], [2], [2,3], [1], [1,3]].
  12. Backtrack to i=1: cur=[1]. INCLUDE nums[1]=2. cur.push(2) → cur=[1,2]. Recurse to i=2.
  13. i=2, cur=[1,2]. Exclude nums[2]=3 — recurse to i=3=n. Leaf! Record [1,2]. ans=[[], [3], [2], [2,3], [1], [1,3], [1,2]].
  14. Back at i=2: INCLUDE nums[2]=3. cur=[1,2,3]. Recurse to i=3=n. Leaf! Record [1,2,3]. Final: all 8 subsets found — [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]].

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Subsets in the editorAll Backtracking problemsBack to roadmap