Build an answer one choice at a time. When a choice leads nowhere, undo it and try the next one.
Used for
holding [ ]
holding [1]
found [1,2]
found [1]
found [2] and [ ]
You hold [1,2] and no numbers are left. What is the next move?
Not quite. At a leaf you record the answer, then step back to the latest decision that still has an untried option.
Step 1 of 7
Goal: list every subset of [1, 2]. At each number we choose: take it or skip it. All the choices form a tree of decisions. Start with nothing chosen.
Step 2 of 7
Choose to take 1.
Step 3 of 7
Take 2 as well. No numbers are left, so write this subset down.
Step 4 of 7
Undo that last choice (the "back" in backtracking) and skip 2 instead. Write [1] down.
Step 5 of 7
Undo taking 1 and skip it instead: holding [ ] again.
Step 6 of 7
From [ ], take or skip 2 the same way: [2] and [ ]. The four leaves are every subset. The recipe is choose, explore, undo. If a choice breaks a rule, stop that branch early (pruning).
Step 7 of 7
Your turn.
RecursionKnight's TourHamiltonian PathCartesian ProductCombinationsPower SetPermutationsCombination Sum ProblemN-Queens Problem
function subsets(nums) { const out = [], path = []; (function go(i) { if (i === nums.length) return out.push([...path]); go(i + 1); // skip path.push(nums[i]); go(i + 1); path.pop(); // take, then undo })(0); return out;}