Backtracking Algorithms - Complete Guide

Backtracking is a algorithmic technique for solving problems recursively by trying to build a solution incrementally and abandoning solutions that fail to satisfy constraints.

What is Backtracking? #

Backtracking is a form of recursion where you:

  1. Make a choice
  2. Explore that path
  3. If it doesn’t work, undo the choice (backtrack)
  4. Try another option

Backtracking Template #

function backtrack(path, choices) {
  // Base case
  if (satisfiesCondition(path)) {
    result.push([...path]);
    return;
  }

  // Try each choice
  for (const choice of choices) {
    // Make choice
    path.push(choice);

    // Explore
    backtrack(path, getNextChoices());

    // Undo choice (backtrack)
    path.pop();
  }
}

Classic Backtracking Problems #

Generate All Subsets #

function subsets(nums) {
  const result = [];

  function backtrack(start, current) {
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

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

console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Generate All Permutations #

function permute(nums) {
  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]);
      const next = remaining.slice(0, i).concat(remaining.slice(i + 1));
      backtrack(current, next);
      current.pop();
    }
  }

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

console.log(permute([1, 2, 3]));
// [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Combination Sum #

function combinationSum(candidates, target) {
  const result = [];

  function backtrack(start, current, sum) {
    if (sum === target) {
      result.push([...current]);
      return;
    }

    if (sum > target) return;

    for (let i = start; i < candidates.length; i++) {
      current.push(candidates[i]);
      backtrack(i, current, sum + candidates[i]);
      current.pop();
    }
  }

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

console.log(combinationSum([2, 3, 6, 7], 7));
// [[2,2,3], [7]]

Letter Combinations of Phone Number #

function letterCombinations(digits) {
  if (!digits) return [];

  const phone = {
    '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
    '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
  };

  const result = [];

  function backtrack(index, current) {
    if (index === digits.length) {
      result.push(current);
      return;
    }

    const letters = phone[digits[index]];
    for (const letter of letters) {
      backtrack(index + 1, current + letter);
    }
  }

  backtrack(0, '');
  return result;
}

console.log(letterCombinations("23"));
// ["ad","ae","af","bd","be","bf","cd","ce","cf"]

N-Queens #

function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill(0).map(() => Array(n).fill('.'));

  function isValid(row, col) {
    // Check column
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }

    // Check diagonal
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }

    // Check anti-diagonal
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false;
    }

    return true;
  }

  function backtrack(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (isValid(row, col)) {
        board[row][col] = 'Q';
        backtrack(row + 1);
        board[row][col] = '.';
      }
    }
  }

  backtrack(0);
  return result;
}

console.log(solveNQueens(4));

Sudoku Solver #

function solveSudoku(board) {
  function isValid(row, col, num) {
    // Check row
    for (let j = 0; j < 9; j++) {
      if (board[row][j] === num) return false;
    }

    // Check column
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === num) return false;
    }

    // Check 3x3 box
    const boxRow = Math.floor(row / 3) * 3;
    const boxCol = Math.floor(col / 3) * 3;
    for (let i = 0; i < 3; i++) {
      for (let j = 0; j < 3; j++) {
        if (board[boxRow + i][boxCol + j] === num) return false;
      }
    }

    return true;
  }

  function backtrack() {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (board[row][col] === '.') {
          for (let num = 1; num <= 9; num++) {
            const char = num.toString();

            if (isValid(row, col, char)) {
              board[row][col] = char;

              if (backtrack()) return true;

              board[row][col] = '.';
            }
          }

          return false;
        }
      }
    }

    return true;
  }

  backtrack();
  return board;
}
function exist(board, word) {
  const rows = board.length;
  const cols = board[0].length;

  function backtrack(row, col, index) {
    if (index === word.length) return true;

    if (row < 0 || row >= rows || col < 0 || col >= cols ||
        board[row][col] !== word[index]) {
      return false;
    }

    const temp = board[row][col];
    board[row][col] = '#';

    const found = backtrack(row + 1, col, index + 1) ||
                  backtrack(row - 1, col, index + 1) ||
                  backtrack(row, col + 1, index + 1) ||
                  backtrack(row, col - 1, index + 1);

    board[row][col] = temp;

    return found;
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (backtrack(i, j, 0)) return true;
    }
  }

  return false;
}

Palindrome Partitioning #

function partition(s) {
  const result = [];

  function isPalindrome(str) {
    let left = 0, right = str.length - 1;
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  function backtrack(start, current) {
    if (start === s.length) {
      result.push([...current]);
      return;
    }

    for (let end = start + 1; end <= s.length; end++) {
      const substring = s.slice(start, end);

      if (isPalindrome(substring)) {
        current.push(substring);
        backtrack(end, current);
        current.pop();
      }
    }
  }

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

console.log(partition("aab"));
// [["a","a","b"], ["aa","b"]]

Generate Parentheses #

function generateParenthesis(n) {
  const result = [];

  function backtrack(current, open, close) {
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }

    if (open < n) {
      backtrack(current + '(', open + 1, close);
    }

    if (close < open) {
      backtrack(current + ')', open, close + 1);
    }
  }

  backtrack('', 0, 0);
  return result;
}

console.log(generateParenthesis(3));
// ["((()))","(()())","(())()","()(())","()()()"]

Restore IP Addresses #

function restoreIpAddresses(s) {
  const result = [];

  function isValid(segment) {
    if (segment.length > 3) return false;
    if (segment[0] === '0' && segment.length > 1) return false;
    return parseInt(segment) <= 255;
  }

  function backtrack(start, current) {
    if (current.length === 4) {
      if (start === s.length) {
        result.push(current.join('.'));
      }
      return;
    }

    for (let len = 1; len <= 3; len++) {
      if (start + len > s.length) break;

      const segment = s.slice(start, start + len);

      if (isValid(segment)) {
        current.push(segment);
        backtrack(start + len, current);
        current.pop();
      }
    }
  }

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

console.log(restoreIpAddresses("25525511135"));
// ["255.255.11.135","255.255.111.35"]

Subsets II (With Duplicates) #

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
  const result = [];

  function backtrack(start, current) {
    result.push([...current]);

    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;

      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

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

console.log(subsetsWithDup([1, 2, 2]));
// [[],[1],[1,2],[1,2,2],[2],[2,2]]

Permutations II (With Duplicates) #

function permuteUnique(nums) {
  nums.sort((a, b) => a - b);
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(current) {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;

      current.push(nums[i]);
      used[i] = true;
      backtrack(current);
      current.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

Combination Sum III #

function combinationSum3(k, n) {
  const result = [];

  function backtrack(start, current, sum) {
    if (current.length === k && sum === n) {
      result.push([...current]);
      return;
    }

    if (current.length >= k || sum >= n) return;

    for (let i = start; i <= 9; i++) {
      current.push(i);
      backtrack(i + 1, current, sum + i);
      current.pop();
    }
  }

  backtrack(1, [], 0);
  return result;
}

console.log(combinationSum3(3, 9));
// [[1,2,6],[1,3,5],[2,3,4]]

Optimization Techniques #

Pruning #

Stop exploring paths that can’t lead to solution:

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = [];

  function backtrack(start, current, sum) {
    if (sum === target) {
      result.push([...current]);
      return;
    }

    for (let i = start; i < candidates.length; i++) {
      // Pruning: skip if sum exceeds target
      if (sum + candidates[i] > target) break;

      current.push(candidates[i]);
      backtrack(i, current, sum + candidates[i]);
      current.pop();
    }
  }

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

Memoization #

Cache results for repeated subproblems:

function wordBreak(s, wordDict) {
  const memo = new Map();
  const wordSet = new Set(wordDict);

  function backtrack(start) {
    if (start === s.length) return true;
    if (memo.has(start)) return memo.get(start);

    for (let end = start + 1; end <= s.length; end++) {
      const word = s.slice(start, end);

      if (wordSet.has(word) && backtrack(end)) {
        memo.set(start, true);
        return true;
      }
    }

    memo.set(start, false);
    return false;
  }

  return backtrack(0);
}

When to Use Backtracking #

  • Constraint satisfaction - Sudoku, N-Queens
  • Combinatorial - Subsets, permutations
  • Path finding - Word search, maze solving
  • Optimization - Maximize/minimize with constraints

Time Complexity #

Backtracking is often exponential:

ProblemTime Complexity
SubsetsO(2^n)
PermutationsO(n!)
Combination SumO(2^n)
N-QueensO(n!)

Tips for Backtracking #

  1. Define base case - When to add result
  2. Make choice - Try each option
  3. Explore - Recursive call
  4. Undo choice - Backtrack
  5. Prune early - Skip invalid paths
  6. Use constraints - Reduce search space
  7. Visualize - Draw decision tree

Backtracking is powerful for exploring all possible solutions. Master these patterns to solve complex combinatorial problems efficiently.

Previous Interval Problems - Complete Guide Trie Data Structure - Complete Guide Next