lthieu's notes

04-Recursion-and-Backtracking

19 min read

Buổi 04 — Recursion & Backtracking

Navigation

← 03-Stack-and-Queue | → 05-Binary-Search Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

1. Analogy & Context

Mental Model — Recursion

Recursion = búp bê matryoshka (búp bê lồng Nga). Mỗi búp bê chứa một búp bê nhỏ hơn bên trong, cho đến khi bạn chạm đến búp bê đặc nhất — không thể mở ra nữa. Đó là base case. Khi bạn giải quyết búp bê nhỏ nhất, bạn lắp lại từng chiếc vào nhau — đó là quá trình unwinding call stack.

Mental Model — Backtracking

Backtracking = giải mê cung. Bạn đi theo một con đường, nếu gặp ngõ cụt (invalid state), bạn quay trở lại (backtrack) điểm rẽ gần nhất và thử hướng khác. Bạn không đi ngẫu nhiên — bạn có hệ thống: thử hết mọi nhánh, prune (cắt) những nhánh chắc chắn không thể dẫn đến đích.

Mối quan hệ Recursion → Backtracking → DP:

Recursion (cơ bản)
    ↓ + "undo state sau mỗi recursive call"
Backtracking (enumerate all valid configurations)
    ↓ + memoization (cache subproblem results)
Top-down Dynamic Programming

Tại sao Backtracking là nền tảng của DP?

  • Backtracking generates all valid configurations — interviewer dùng để test “can you enumerate all possibilities systematically?”
  • Khi bạn thêm memoization vào backtracking, bạn có top-down DP.
  • N-Queens, Sudoku Solver, Word Search — đây là những bài kinh điển FAANG.

2. The FAANG Standard

Backtracking ở FAANG Interviews

  • Xuất hiện trong ~15% Hard problems và ~20% Medium problems.
  • Interviewer kiểm tra: bạn có biết khi nào prune không? Pruning là dấu hiệu của kỹ sư có kinh nghiệm.
  • N-Queens là bài FAANG hỏi để kiểm tra tư duy combinatorial toàn diện.
  • Vẽ recursion tree khi giải thích = cách bạn communicate solution trong phỏng vấn.

Công thức chung của Backtracking:

function backtrack(state, choices):
    if is_complete(state):
        record(state) → add to results
        return

    for each choice in valid_choices(state):
        make_choice(state, choice)      ← Thay đổi state
        backtrack(new_state)
        undo_choice(state, choice)      ← PHẢI undo! Đây là "backtrack"

Điểm khác biệt Recursion vs Backtracking

  • Recursion thuần: không có “undo”. Bạn chỉ tính và trả kết quả lên.
  • Backtracking: bắt buộc có “undo” sau mỗi đệ quy. State phải được restore về trước khi thử choice đó. Đây là lý do gọi là “backtrack”.

3. Visual Thinking

Recursion Tree cho fib(4)

graph TD
    F4["fib(4)"] --> F3L["fib(3)"]
    F4 --> F2A["fib(2)"]
    F3L --> F2B["fib(2)"]
    F3L --> F1A["fib(1)=1"]
    F2A --> F1B["fib(1)=1"]
    F2A --> F0A["fib(0)=0"]
    F2B --> F1C["fib(1)=1"]
    F2B --> F0B["fib(0)=0"]

    style F4 fill:#4A90D9,color:#fff
    style F2A fill:#E74C3C,color:#fff
    style F2B fill:#E74C3C,color:#fff

Overlapping Subproblems

fib(2) được tính 2 lần (màu đỏ). fib(1) và fib(0) còn bị tính nhiều lần hơn. Đây là lý do naive recursion là — exponential. Memoization cache các kết quả này, cắt xuống .

Backtracking Decision Tree — permutations([1,2,3])

graph TD
    ROOT["[]"] --> A1["[1]"]
    ROOT --> B1["[2]"]
    ROOT --> C1["[3]"]

    A1 --> A12["[1,2]"]
    A1 --> A13["[1,3]"]
    B1 --> B21["[2,1]"]
    B1 --> B23["[2,3]"]
    C1 --> C31["[3,1]"]
    C1 --> C32["[3,2]"]

    A12 --> R123["[1,2,3] RESULT"]
    A13 --> R132["[1,3,2] RESULT"]
    B21 --> R213["[2,1,3] RESULT"]
    B23 --> R231["[2,3,1] RESULT"]
    C31 --> R312["[3,1,2] RESULT"]
    C32 --> R321["[3,2,1] RESULT"]

    style R123 fill:#27AE60,color:#fff
    style R132 fill:#27AE60,color:#fff
    style R213 fill:#27AE60,color:#fff
    style R231 fill:#27AE60,color:#fff
    style R312 fill:#27AE60,color:#fff
    style R321 fill:#27AE60,color:#fff

Pruning — N-Queens (n=4): Cắt Bớt Nhánh Vô Hiệu

graph TD
    ROOT["Row 0: đặt Queen tại cột nào?"]
    ROOT --> C0["Col 0 — thử"]
    ROOT --> C1["Col 1 — thử"]
    ROOT --> C2["Col 2 — PRUNED"]
    ROOT --> C3["Col 3 — PRUNED"]

    C0 --> R1C2["Row 1: Col 2 — thử"]
    C0 --> R1X["Row 1: Col 0,1,3 — bị tấn công"]

    R1C2 --> R2X["Row 2: TẤT CẢ bị tấn công"]

    C1 --> R1C3["Row 1: Col 3 — thử"]
    R1C3 --> R2C0["Row 2: Col 0 — thử"]
    R2C0 --> R3C2["Row 3: Col 2 → VALID: [1,3,0,2]"]

    style C2 fill:#CCCCCC,color:#666
    style C3 fill:#CCCCCC,color:#666
    style R1X fill:#FFB3B3,color:#666
    style R2X fill:#FFB3B3,color:#666
    style R3C2 fill:#27AE60,color:#fff

4. TypeScript Template

4.1 — Fibonacci: Naive O(2^N) → Memoized O(N) → Bottom-up O(1) space

/**
 * Fibonacci — 3 approaches, từ naive đến optimal
 * Minh họa quá trình tối ưu hóa recursion.
 */
 
// NAIVE — O(2^N) time, O(N) space (call stack depth)
// Tính lại subproblems nhiều lần → exponential blowup
function fibNaive(n: number): number {
  if (n <= 1) return n; // Base case
  return fibNaive(n - 1) + fibNaive(n - 2);
  // fib(50) với approach này: ~2^50 = 10^15 calls → timeout
}
 
// MEMOIZED TOP-DOWN — O(N) time, O(N) space
// Cache kết quả đã tính → mỗi subproblem chỉ tính 1 lần
function fibMemo(n: number, memo: Map<number, number> = new Map()): number {
  if (n <= 1) return n;
 
  // Cache hit: đã tính rồi, trả ngay mà không tính lại
  if (memo.has(n)) return memo.get(n)!;
 
  // Cache miss: tính và lưu vào cache trước khi return
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}
 
// BOTTOM-UP DP — O(N) time, O(1) space (tối ưu nhất)
// Không cần recursion hay cache lớn — chỉ lưu 2 giá trị
function fibDP(n: number): number {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}
 
/*
 * TRANSFORMATION PATTERN (áp dụng cho MỌI overlapping-subproblem recursion):
 * 1. Nhận ra: subproblems bị tính lại nhiều lần trong recursion tree.
 * 2. Thêm memo map làm parameter (hoặc closure).
 * 3. Check cache trước khi tính.
 * 4. Lưu kết quả vào cache trước khi return.
 * → O(2^N) → O(N) chỉ với 4 dòng code thêm vào.
 */

4.2 — Generate All Permutations

/**
 * LeetCode #46 — Permutations
 *
 * APPROACH: Backtracking với used[] array
 * - used[i] = true: nums[i] đã được chọn vào path hiện tại
 * - Tại mỗi bước: thử mọi nums[i] chưa được chọn
 * - Khi path.length === nums.length: lưu kết quả
 * - SAU đệ quy: PHẢI undo — path.pop(), used[i] = false
 *
 * Time: O(N! * N) — N! permutations, copy mỗi cái O(N)
 * Space: O(N) — call stack depth + used array
 *
 * @param nums - Array số nguyên phân biệt
 * @returns Tất cả N! permutations
 */
function permute(nums: number[]): number[][] {
  const result: number[][] = [];
  const path: number[] = [];
  const used: boolean[] = new Array(nums.length).fill(false);
 
  function backtrack(): void {
    // Base case: path chứa đủ N số → một permutation hoàn chỉnh
    if (path.length === nums.length) {
      result.push([...path]); // Clone! Không push reference
      return;
    }
 
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // Bỏ qua số đã dùng trong path hiện tại
 
      // CHOOSE: thêm nums[i] vào path
      used[i] = true;
      path.push(nums[i]);
 
      // EXPLORE: tiếp tục với số chưa dùng
      backtrack();
 
      // UNCHOOSE (backtrack!): restore state
      path.pop();
      used[i] = false;
    }
  }
 
  backtrack();
  return result;
}

4.3 — Subsets (Power Set) — Include/Exclude Pattern

/**
 * LeetCode #78 — Subsets
 *
 * PATTERN: Include/Exclude — tại mỗi index, có 2 lựa chọn:
 * - INCLUDE nums[startIndex] vào current subset
 * - EXCLUDE nums[startIndex] (chuyển qua startIndex+1)
 *
 * Đây là pattern cơ bản nhất của backtracking.
 * Mọi node của recursion tree là một valid subset.
 *
 * Time: O(2^N * N) — 2^N subsets, mỗi cái copy O(N)
 * Space: O(N) — call stack depth tối đa N
 *
 * @example
 * subsets([1,2,3]) → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
 */
function subsets(nums: number[]): number[][] {
  const result: number[][] = [];
  const current: number[] = [];
 
  function backtrack(startIndex: number): void {
    // Mỗi state là một valid subset — thêm vào result ngay (không cần base case riêng)
    result.push([...current]);
 
    for (let i = startIndex; i < nums.length; i++) {
      current.push(nums[i]);  // Include nums[i]
      backtrack(i + 1);       // Chỉ xét elements SAU i (tránh duplicate subsets)
      current.pop();          // Exclude nums[i] (backtrack)
    }
  }
 
  backtrack(0);
  return result;
}
 
/*
 * Recursion trace cho [1,2,3]:
 * backtrack(0): result=[[]], current=[]
 *   push(1): current=[1]
 *     backtrack(1): result=[[],[1]], current=[1]
 *       push(2): current=[1,2]
 *         backtrack(2): result=[[],[1],[1,2]], current=[1,2]
 *           push(3): backtrack(3): result=[[],[1],[1,2],[1,2,3]]
 *           pop(3): current=[1,2]
 *         pop(2): current=[1]
 *       push(3): current=[1,3]
 *         backtrack(3): result=[...,[1,3]]
 *         pop(3): current=[1]
 *     pop(1): current=[]
 *   push(2), push(3) → tương tự
 */

4.4 — Combination Sum với Duplicate Pruning

/**
 * LeetCode #39 — Combination Sum
 *
 * Tìm tất cả combinations của candidates có tổng = target.
 * Mỗi candidate có thể dùng nhiều lần (unlimited use).
 *
 * PRUNING KEY: Sort candidates trước.
 * Nếu candidates[i] > remaining → break (không phải continue!).
 * Vì candidates đã sort tăng dần, mọi element sau cũng > remaining → bỏ hết.
 *
 * Time: O(N^(T/M)) — T=target, M=min candidate
 *   (chiều sâu tối đa T/M, mỗi level N nhánh)
 * Space: O(T/M) — call stack depth tối đa
 *
 * @param candidates - Array số nguyên dương
 * @param target - Tổng cần đạt
 */
function combinationSum(candidates: number[], target: number): number[][] {
  const result: number[][] = [];
  const current: number[] = [];
 
  candidates.sort((a, b) => a - b); // Sort để pruning hoạt động
 
  function backtrack(startIndex: number, remaining: number): void {
    if (remaining === 0) {
      result.push([...current]);
      return;
    }
 
    for (let i = startIndex; i < candidates.length; i++) {
      // PRUNING: nếu candidate hiện tại > remaining, không cần thử tiếp
      // Dùng break vì array đã sorted — mọi element sau cũng > remaining
      if (candidates[i] > remaining) break;
 
      current.push(candidates[i]);
      backtrack(i, remaining - candidates[i]); // i (không phải i+1) — dùng lại được
      current.pop();
    }
  }
 
  backtrack(0, target);
  return result;
}

4.5 — N-Queens Full Solution (LeetCode #51)

/**
 * LeetCode #51 — N-Queens
 *
 * ĐỀ BÀI: Đặt N queens trên bàn cờ N×N sao cho không queen nào tấn công nhau.
 * Queens tấn công theo: hàng ngang, cột dọc, và cả hai đường chéo.
 *
 * APPROACH: Backtracking row-by-row
 * - Đặt đúng 1 queen mỗi hàng → loại bỏ conflict theo hàng từ đầu.
 * - Tại mỗi hàng: thử từng cột.
 * - CHECK CONFLICT với O(1) dùng 3 sets:
 *   - cols: set các cột đã bị chiếm.
 *   - diag1: set (col - row) — hằng số trên đường chéo "/"
 *   - diag2: set (col + row) — hằng số trên đường chéo "\"
 *
 * Time: O(N!) với pruning, thực tế tốt hơn nhiều
 * Space: O(N^2) — board O(N^2) + 3 sets O(N) + call stack O(N)
 *
 * @param n - Kích thước bàn cờ và số queens
 * @returns Tất cả configurations hợp lệ dưới dạng array of strings
 *
 * @example
 * solveNQueens(4) → [
 *   [".Q..","...Q","Q...","..Q."],
 *   ["..Q.","Q...","...Q",".Q.."]
 * ]
 */
function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));
 
  // 3 sets để check conflict trong O(1) — không cần scan board
  const cols = new Set<number>();    // Cột đã bị chiếm
  const diag1 = new Set<number>();  // col - row (đường chéo /)
  const diag2 = new Set<number>();  // col + row (đường chéo \)
 
  /** Chuyển board hiện tại thành array of strings để lưu kết quả */
  const buildBoard = (): string[] => board.map(row => row.join(''));
 
  /**
   * Đặt queen cho từng hàng từ 0 đến n-1.
   * @param row - Hàng hiện tại (0-indexed)
   */
  function backtrack(row: number): void {
    // Base case: đã đặt queen cho tất cả N hàng → valid solution
    if (row === n) {
      result.push(buildBoard());
      return;
    }
 
    for (let col = 0; col < n; col++) {
      // PRUNING: kiểm tra (row, col) có bị tấn công không
      if (cols.has(col) || diag1.has(col - row) || diag2.has(col + row)) {
        continue; // Bị tấn công → bỏ qua, thử cột khác
      }
 
      // PLACE queen
      board[row][col] = 'Q';
      cols.add(col);
      diag1.add(col - row);
      diag2.add(col + row);
 
      // EXPLORE next row
      backtrack(row + 1);
 
      // REMOVE queen (backtrack — restore state)
      board[row][col] = '.';
      cols.delete(col);
      diag1.delete(col - row);
      diag2.delete(col + row);
    }
  }
 
  backtrack(0);
  return result;
}
 
/*
 * TRACE THROUGH với n=4:
 *
 * Row 0, Col 0: Q...
 *   Row 1, Col 1: conflict (diag2: 0+0=0, 1+1=2 != 0... wait)
 *     Actually Col 1: diag1 = 1-1=0, diag1 has 0-0=0 → conflict (same diag1)
 *     Col 2: diag1=2-1=1, diag2=2+1=3, cols={0} → OK
 *     Row 1, Col 2: Q... | ..Q.
 *       Row 2: col 0 (diag2=0+2=2, diag2 has 2+0=2? No. cols={0,2})
 *         col 0: cols has 0 → skip
 *         col 1: diag2=1+2=3, diag2 has 2+1=3 → conflict
 *         col 2: cols has 2 → skip
 *         col 3: diag1=3-2=1, diag1 has 2-1=1 → conflict
 *       → No valid column for row 2 → backtrack
 *     Col 3: diag1=3-1=2, diag2=3+1=4, cols={0} → OK
 *     Row 1, Col 3: Q... | ...Q
 *       Row 2: Col 1: diag1=1-2=-1, diag2=1+2=3, cols={0,3} → OK
 *         Row 3: Col 2: diag1=2-3=-1 → conflict with row2 col1 (-1)
 *                Col other: all conflict
 *       → backtrack
 *   → No solution with Row 0 Col 0
 *
 * Row 0, Col 1: .Q..
 *   Row 1, Col 3: diag1=3-1=2, diag2=3+1=4, cols={1} → OK
 *     Row 2, Col 0: diag1=0-2=-2, diag2=0+2=2, cols={1,3} → OK
 *       Row 3, Col 2: diag1=2-3=-1, diag2=2+3=5, cols={1,3,0} → OK
 *       → SOLUTION: [".Q..","...Q","Q...","..Q."] ✓
 *
 * → Tổng: 2 solutions cho n=4
 */

4.6 — Word Search trên Grid

/**
 * LeetCode #79 — Word Search
 *
 * Tìm xem word có tồn tại trong grid (4-directional path) không.
 * Mỗi cell chỉ được dùng 1 lần trong mỗi path.
 *
 * APPROACH: DFS + Backtracking từ mỗi starting cell
 * - Đánh dấu cell đang visit bằng sentinel '#'.
 * - Nếu không dẫn đến solution: unmark (backtrack).
 *
 * Time: O(M*N * 4^L) — M*N cells là starting points, L = word.length
 * Space: O(L) — recursion depth tối đa L
 *
 * @param board - Grid ký tự
 * @param word - Từ cần tìm
 */
function exist(board: string[][], word: string): boolean {
  const rows = board.length;
  const cols = board[0].length;
  const DIRS = [[0,1],[0,-1],[1,0],[-1,0]];
 
  function dfs(row: number, col: number, index: number): boolean {
    // Base case: đã match hết tất cả ký tự
    if (index === word.length) return true;
 
    // Boundary check + character match
    if (row < 0 || row >= rows || col < 0 || col >= cols) return false;
    if (board[row][col] !== word[index]) return false;
 
    // Mark as visited — dùng '#' làm sentinel để tránh dùng lại
    const temp = board[row][col];
    board[row][col] = '#';
 
    // Explore 4 directions
    for (const [dr, dc] of DIRS) {
      if (dfs(row + dr, col + dc, index + 1)) {
        board[row][col] = temp; // Restore trước khi return true
        return true;
      }
    }
 
    // Unmark (backtrack) — không tìm thấy từ cell này
    board[row][col] = temp;
    return false;
  }
 
  // Thử mọi cell làm starting point
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (dfs(r, c, 0)) return true;
    }
  }
 
  return false;
}

5. Complexity Deep-dive

Tổng quan Complexity

Bài toánTime ComplexitySpace ComplexityGhi chú
Permutations permutations, copy mỗi cái
Subsets subsets, copy mỗi cái
Combination Sum=target, =min element
N-QueensVới pruning, thực tế tốt hơn nhiều
Word Search starts, =word length

Memoization: → cho Fibonacci

Tại sao Memoization hiệu quả?

Naive Fibonacci: → giải ra

Số unique subproblems: chỉ giá trị cần tính:

Với Memoization: mỗi subproblem tính đúng 1 lần → total work

Tổng quát: Nếu có unique subproblems, mỗi cái cần work → Total =

Pruning Effect trên N-Queens

Không prune (theoretical)Với 3-set pruning
4~8 nodes explored
8~2,057 nodes
12~856,188 nodes
15~2.28B nodes

Pruning là yếu tố then chốt

N-Queens về lý thuyết là , nhưng với 3 sets để check conflicts trong , pruning cắt đi phần lớn search space. Sự khác biệt giữa “giải được” và “timeout” với phụ thuộc vào việc bạn có dùng conflict check hay không.

6. Edge Cases & Pitfalls

Pitfall 1: Missing Base Case → Stack Overflow 

// SAI — không có base case → đệ quy vô hạn → stack overflow
function factorial(n: number): number {
  return n * factorial(n - 1); // Gọi mãi mãi!
}
 
// ĐÚNG — base case rõ ràng, phải xác định TRƯỚC khi viết recursive case
function factorial(n: number): number {
  if (n <= 1) return 1; // BASE CASE — khi nào dừng?
  return n * factorial(n - 1);
}

Pitfall 2: Không Restore State Sau Backtrack 

// SAI — push vào path nhưng quên pop → state bị "ô nhiễm"
for (let i = 0; i < nums.length; i++) {
  if (used[i]) continue;
  used[i] = true;
  path.push(nums[i]);
  backtrack(path, nums, used);
  // MISSING: path.pop() và used[i] = false
  // → path và used không được reset → kết quả sai hoàn toàn
}
 
// ĐÚNG — luôn có cặp choose / unchoose đối xứng
used[i] = true;
path.push(nums[i]);
backtrack(path, nums, used);
path.pop();          // PHẢI CÓ — restore path
used[i] = false;     // PHẢI CÓ — restore used

Pitfall 3: Không Clone Khi Thêm vào Result 

// SAI — push reference, sau đó backtrack modify path → result cũng bị thay đổi!
result.push(path); // path là mutable reference
 
// ĐÚNG — clone array trước khi thêm vào result
result.push([...path]);    // Spread operator — shallow copy
result.push(path.slice()); // Hoặc: Array.slice()

Pitfall 4: Duplicates Trong Input → Duplicate Results 

// Input [1,1,2] với Permutations → sinh ra [1,1,2] hai lần nếu không xử lý
 
// FIX: Sort + skip khi nums[i] === nums[i-1] và nums[i-1] chưa được dùng
nums.sort((a, b) => a - b); // Sort trước — BẮT BUỘC
 
for (let i = 0; i < nums.length; i++) {
  if (used[i]) continue;
  // Skip nếu: giá trị giống element trước VÀ element trước CHƯA được dùng
  // (nghĩa là ta đã xét branch dùng nums[i-1] ở vị trí này rồi)
  if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) continue;
 
  used[i] = true;
  path.push(nums[i]);
  backtrack();
  path.pop();
  used[i] = false;
}

Pitfall 5: Cycle trong Grid DFS — Không Đánh Dấu Visited 

// SAI — không đánh dấu visited → dfs có thể đi lại cell cũ vô hạn
function dfs(r: number, c: number, idx: number): boolean {
  if (board[r][c] !== word[idx]) return false;
  // Tiếp tục mà không mark → có thể quay lại (r,c) từ neighbor
  return dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1); // Cycle!
}
 
// ĐÚNG — mark trước explore, unmark sau explore
const temp = board[r][c];
board[r][c] = '#';    // Mark: không dùng lại trong path này
const found = dfs(r+1, c, idx+1) || dfs(r-1, c, idx+1);
board[r][c] = temp;   // Unmark (backtrack)
return found;

7. Pattern Recognition

Nhận Diện Backtracking Problems

Từ khóaPatternLeetCode
”all permutations”Backtrack với used[] array#46, #47
”all subsets / power set”Include/exclude với startIndex#78, #90
”combination sum”Backtrack + remaining + pruning#39, #40
”all valid configurations”N-Queens style, row-by-row#51, #52
”word search in grid”DFS + mark/unmark grid cell#79, #212
”palindrome partitioning”Backtrack + isPalindrome check#131
”generate parentheses”Backtrack với open/close counts#22
”sudoku solver”Grid backtrack + row/col/box check#37
”letter combinations”Backtrack với phone keypad map#17
”restore IP addresses”Backtrack với segment count#93

Khi nào KHÔNG dùng Backtracking?

  • Chỉ cần đếm số lượng (không cần list hết): → thường có DP hoặc tốt hơn.
  • Decision problem với overlapping subproblems: → Memoization / DP.
  • N lớn (> 20): backtracking sẽ timeout — cần approach khác.

Backtracking phù hợp nhất khi: cần enumerate all solutions và nhỏ ().

Backtracking Template Tổng quát 

function backtrack(state):
    if is_goal(state):
        record(state)
        return
    for choice in get_choices(state):
        if is_valid(choice, state):
            apply(choice, state)   ← Make move
            backtrack(new_state)
            undo(choice, state)    ← Unmake move (KEY!)

Template này áp dụng cho tất cả backtracking problems. Chỉ khác nhau ở is_goal, get_choices, is_valid, apply, và undo.

8. Top LeetCode Problems

#TênĐộ khóPatternPriority
46PermutationsMediumused[] backtrackMust-do
78SubsetsMediumInclude/exclude + startIndexMust-do
39Combination SumMediumstartIndex + remaining + pruningMust-do
22Generate ParenthesesMediumBacktrack + open/close countMust-do
79Word SearchMediumGrid DFS + mark/unmarkHigh
131Palindrome PartitioningMediumBacktrack + palindrome checkHigh
47Permutations IIMediumSort + skip duplicatesHigh
90Subsets IIMediumSort + skip duplicatesHigh
17Letter Combinations of Phone NumberMediumKeypad map + backtrackMedium
51N-QueensHardRow-by-row + 3 sets O(1) checkStretch
37Sudoku SolverHardGrid backtrack + constraint checkStretch

Lộ trình học tối ưu

  1. Làm #78 (Subsets) → hiểu include/exclude và startIndex pattern.
  2. Làm #46 (Permutations) → hiểu used[] tracking và choose/unchoose.
  3. Làm #39 (Combination Sum) → hiểu pruning với sorted array.
  4. Làm #22 (Generate Parentheses) → backtrack với numeric constraints.
  5. Thử #51 (N-Queens) → tổng hợp: row-by-row, 3 sets, pruning toàn diện.

9. Self-Assessment Checklist

Checklist trước khi chuyển sang buổi tiếp theo

Kiến thức nền:

  • Giải thích “base case” và “recursive case” — tại sao thiếu base case gây stack overflow?
  • Vẽ recursion tree cho fib(5) — chỉ ra overlapping subproblems.
  • Giải thích backtracking template: choose → explore → unchoose.
  • Giải thích tại sao phải clone array khi thêm vào result.

Code từ memory (không nhìn):

  • Viết được subsets([1,2,3]) với include/exclude trong < 8 phút.
  • Viết được permute([1,2,3]) với used[] trong < 8 phút.
  • Viết được combinationSum với startIndex và pruning trong < 10 phút.
  • Viết được fibMemo (memoized) trong < 5 phút.

Hiểu sâu:

  • Trace through solveNQueens(4) bằng tay — giải thích tại sao chỉ có 2 solutions.
  • Giải thích 3 sets trong N-Queens — tại sao col - row là constant trên đường chéo ”/“?
  • Giải thích sort + skip duplicate trick cho Permutations II (#47) bằng một ví dụ cụ thể.
  • Mô tả từng bước của exist(board, "ABCCED") trên grid nhỏ 3×4.

Stretch goal:

  • Solve được #37 Sudoku Solver mà không nhìn solution.
  • Implement Word Search II (#212) với Trie optimization để giảm từ xuống .
  • Giải thích tại sao Backtracking + Memoization = Top-down DP — cho một ví dụ cụ thể.

Xem tiếp: 05-Binary-Search — Từ O(N) xuống O(log N) — tư duy “loại bỏ nửa search space mỗi bước”

Graph View

Backlinks