Backtracking mencoba semua kemungkinan secara sistematis: coba → jika gagal, mundur (backtrack) → coba yang lain.

Analogi: Mencari jalan keluar dari labirin — jika buntu, kembali ke persimpangan terakhir.

Pola dasar:

function backtrack(candidates, current, result) {
  if (isSolution(current)) {
    result.push([...current]);
    return;
  }

  for (const candidate of candidates) {
    if (isValid(candidate, current)) {
      current.push(candidate);     // Coba
      backtrack(candidates, current, result);
      current.pop();               // Backtrack!
    }
  }
}

Contoh 1: Generate semua permutasi

function permutations(arr) {
  const result = [];

  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop(); // Backtrack
    }
  }

  backtrack([], arr);
  return result;
}

permutations([1, 2, 3]);
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Contoh 2: N-Queens (simplified)

function solveNQueens(n) {
  const board = Array(n).fill(-1); // board[row] = column
  const solutions = [];

  function isSafe(row, col) {
    for (let r = 0; r < row; r++) {
      if (board[r] === col) return false;
      if (Math.abs(board[r] - col) === Math.abs(r - row)) return false;
    }
    return true;
  }

  function solve(row) {
    if (row === n) {
      solutions.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      if (isSafe(row, col)) {
        board[row] = col;
        solve(row + 1);
        board[row] = -1; // Backtrack
      }
    }
  }

  solve(0);
  return solutions;
}

Kegunaan nyata:

• Sudoku solver
• Maze solving
• Constraint satisfaction (scheduling, coloring)
• Subset/combination generation

🎭 Analogi sehari-hari (selain labirin): Coba password kombinasi keys di smart lock. Kamu coba angka 1, dengar bunyi yang benar, lanjut ke digit kedua. Salah? Kembali ke digit pertama, ganti angka. Sistematis cek semua kemungkinan. Itulah backtracking — trial and error dengan progress yang dicatat.

💡 Backtracking vs Brute Force: Brute force generate semua kombinasi lalu cek. Backtracking prune cabang yang sudah jelas salah lebih awal — gak buang waktu generate kombinasi yang gak mungkin valid. Speedup massive untuk constraint problems.

⚠️ Jebakan umum:

• Lupa undo state setelah recursive call (current.pop() setelah current.push()) = state corrupt
• Pruning lemah = effectively brute force = O(eksponensial) tetap lambat
• Exponential time — backtracking inherently 2ⁿ atau n!. Untuk n besar (>20), perlu memo/DP atau approximation
• Mutate vs copy — mutate state lebih cepat tapi lebih bug-prone

🎯 Pola "ini backtracking":

• "Generate semua permutations / combinations / subsets" → backtracking
• "Cari path di maze/grid" → backtracking
• "Sudoku / Crossword / Constraint puzzle" → backtracking
• "N-Queens / Coloring" → backtracking
• "Word break / Pattern match" → bisa backtracking + memoization

🧪 Tebakan cepat: N-Queens N=8. Brute force: 8⁸ = 16jt. Backtracking dengan pruning isSafe: ~2 ribu (10000x lebih sedikit). Power of pruning.

TL;DR: Backtracking = trial-and-error dengan undo (backtrack). Power-nya di pruning awal. Cocok untuk constraint problems, generate semua solusi. Inherently exponential — pakai memo kalau ada subproblem overlap.