Subsets / Combinations
At each index either take the element or skip it, recursing on the rest and undoing the choice on the way back.
Recursion & BacktrackingO(2^n) subsets, O(n) per outputNew17 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
all subsets
combination sum
partition into groups
The template
Get this into muscle memory, then adapt the condition per problem.
function dfs(i: number, cur: number[]) {
if (i === n) { out.push([...cur]); return; }
cur.push(a[i]); dfs(i + 1, cur); cur.pop();
dfs(i + 1, cur);
} Watch Subsets (Take or Skip)If you are stuck
The generic hint ladder for this pattern, in order.
- 1Every element is either in or out, which is a binary decision tree.
- 2Copy the current path when you record it, or later mutations corrupt it.
- 3Sort first and skip equal siblings when the input has duplicates.
Drill it
Every problem in the bank that uses this pattern.
0 / 17 solved