Forward index

Use this when recursion moves forward through an array or string. The same shape covers subsets, combinations, target sums, and string splits.

Template

dfs(start):
    if current state is an answer:
        add path
 
    for i = start; i < n; i++:
        if choice i is invalid:
            continue or break
 
        choose i
        dfs(next_start)
        undo

Problems

Subsets

Problem: generate all subsets of distinct numbers.

Pattern: either add path at every recursion node with a start-index loop, or use pick-skip recursion where each index has two choices.

Optimizations: none needed beyond copying path only when recording an answer. This is inherently 2^n because every subset must be produced.

dfs(start):
    ans.push(path)
 
    for i = start; i < n; i++:
        path.push(nums[i])
        dfs(i + 1)
        path.pop()

Subsets II

Problem: generate all unique subsets when numbers may repeat.

Pattern: sort first, then skip duplicate values at the same depth.

for i = start; i < n; i++:
    if i > start and nums[i] == nums[i - 1]:
        continue

Idea is that in the same “dfs” depth, we don’t choose it again.

Combinations

Problem: choose k numbers from 1..n.

Same as above exccept we don’t store each path.

Pattern: loop from start, recurse with x + 1, stop when path.size == k.

Optimizations: stop the loop early when there are not enough remaining numbers to fill k.

Combination Sum

Problem: find combinations that sum to target, with unlimited reuse.

Pattern: sort, break when value exceeds remaining sum, recurse with i.

Optimizations: sort so nums[i] > remain can break; ignore candidates larger than the target; if duplicate candidate values exist, dedupe them first.

Combination Sum II

Problem: find unique combinations that sum to target, using each value once.

Pattern: sort, skip duplicates at the same depth, recurse with i + 1.

Optimizations: sort for both duplicate skipping and early break when the value exceeds remain.

Combination Sum III

Problem: choose exactly k values from 1..9 that sum to target.

Pattern: start-index combinations plus both remaining sum and size constraints.

Optimizations: stop when path.size == k, remain < 0, or not enough numbers remain. You can also prune by min/max possible sums for the remaining count.

Palindrome Partitioning

Problem: split a string so every piece is a palindrome.

Pattern: start is the next uncut position; try every valid next cut.

Optimizations: precompute is_pal[start][end] with DP so palindrome checks are O(1), instead of rescanning each substring.

dfs(start):
    if start == n:
        ans.push(path)
        return
 
    for end = start; end < n; end++:
        if is_palindrome(start, end):
            path.push(s[start..end])
            dfs(end + 1)
            path.pop()

Restore IP Addresses

Problem: split a string into four valid IP address parts.

Pattern: try cuts of length 1..3, track part count, reject leading zeroes and values over 255.

Optimizations: prune by remaining length. If there are parts_left, remaining characters must be between parts_left and 3 * parts_left.

Word Break II

Problem: return all sentences formed by dictionary words.

Pattern: cut valid dictionary words; memoize start because many suffixes repeat.

Optimizations: memoization is required for a good interview answer. Store all sentences possible from each start.

Lest I Forget

Forward Index