Learn All Patterns of Subsequences (Theory)
EasyThe take / not-take skeleton
Problem
Learn the take/not-take recursion pattern that generates and evaluates all subsequences of an array.
At each element you branch two ways: take it or skip it.
The idea
Every subsequence problem is the same recursion: at index i either take the element and recurse on i+1 with the updated state, or skip it and recurse on i+1 unchanged. What changes between problems is only what you carry and what you return at the base case.
The trick
- Generate, count, or optimise — the branching is identical, only the return value differs.
- Base case is i == n; whether it returns 1, 0 or the accumulated list is problem-specific.
- Adding memoisation on (i, state) is what turns it into dynamic programming.
Step 1 of 9. At each index, branch two ways: skip the element (left) or take it (right). The leaves are all subsequences of [1, 2].
1/9
Optimal
timeO(2ⁿ)spaceO(n)
Branch on each element.
1function go(i, path) {2 if (i === n) { emit(path); return; }3 go(i + 1, path); // don't take4 go(i + 1, [...path, a[i]]); // take5}Input
- nodes
- 7, 6 edges
Output
- output
- —
- count
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Example
- Input:
- [3,1,2]
- Output:
- 8 subsequences generated
Finished the walkthrough? Add it to your streak.