Pattern-Recursion-DC

Pattern — Recursion & Divide & Conquer

Khi nào dùng

Bài có substructure: bài nhỏ tương tự bài lớn + có thể combine kết quả. Recursion = “tin con sẽ làm đúng”.

Recursion templates

1. Tree-style recursion (return value)

function dfs(node: TreeNode | null): T {
  if (node === null) return baseCase;
  const left = dfs(node.left);
  const right = dfs(node.right);
  return combine(node.val, left, right);
}

2. Backtracking (state mutation)

function backtrack(state: State): void {
  if (isComplete(state)) { result.push(snapshot(state)); return; }
  for (const choice of choices(state)) {
    if (!isValid(choice, state)) continue;
    apply(choice, state);
    backtrack(state);
    undo(choice, state);  // revert!
  }
}

3. Divide & Conquer

function solve(arr: T[], lo: number, hi: number): R {
  if (lo >= hi) return baseCase;
  const mid = lo + ((hi - lo) >> 1);
  const left  = solve(arr, lo, mid);
  const right = solve(arr, mid + 1, hi);
  return merge(left, right);
}

Top problems

Bài	LC	Pattern
Subsets	LC #78	Backtrack + include/exclude
Permutations	LC #46	Backtrack + visited
Combination Sum	LC #39	Backtrack + same index
N-Queens	LC #51	Backtrack + 3 sets (col, diag1, diag2)
Word Search	LC #79	Backtrack on grid
Merge Sort	—	D&C + merge
Quick Sort	—	D&C + partition
Maximum Subarray	LC #53	D&C O(N log N) hoặc Kadane O(N)
Different Ways to Add Parentheses	LC #241	D&C on operator
Construct Tree from Pre/In	LC #105	D&C + map

Pitfalls

1. Forget to undo trong backtrack → state corruption.
2. Reference vs copy: trong JS, result.push(state) push reference — phải result.push([...state]) để snapshot.
3. Stack overflow: dfs quá sâu (>10^4) → convert sang iterative.
4. Re-compute substructure: nếu cùng (state) lặp lại → memo (đó là DP).

Khi nào D&C → DP?

D&C có overlapping subproblems → memoization → top-down DP. Vd: fib O(2^N) D&C → O(N) DP.

→ Nguồn: 04-Recursion-and-Backtracking, 05-Divide-and-Conquer