Using Backtracking Pattern

1. Understanding Backtracking Framework

Component	Description	Usage
State Space Tree	Represents all possible solutions in a tree structure where each node is a partial solution.	Used to visualize and explore all valid paths to a solution.
Choice Function	Defines the set of choices available at each node in the state space tree.	Guides the exploration by specifying valid moves from a given state.
Constraint Function	Checks whether a partial solution can lead to a valid complete solution.	Prunes branches that cannot lead to a solution early in the search process.
Solution Function	Verifies if a complete solution has been found.	Determines when the backtracking algorithm should stop or continue exploring.

Example: N-Queens Problem

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

  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 1) return false;
      if (col - (row - i) >= 0 && board[i][col - (row - i)] === 1) return false;
      if (col + (row - i) < n && board[i][col + (row - i)] === 1) return false;
    }
    return true;
  }

  function backtrack(row) {
    if (row === n) {
      result.push(board.map(row => [...row]));
      return;
    }

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

  backtrack(0);
  return result;
}

Key Concepts

Recursive Exploration: Backtracking uses recursion to explore all possible solutions.
Pruning: Invalid paths are pruned early to reduce search space.
State Management: Each recursive call maintains a partial solution state.
Solution Validation: A complete solution is confirmed using a solution function.

2. Solving N-Queens Problem

The N-Queens problem involves placing N queens on an N×N chessboard such that no two queens threaten each other. This is a classic backtracking problem.

Property	Description	Value
Board Size	Size of the chessboard (N×N)	`N`
Constraint	Queens must not share rows, columns, or diagonals	None

Example: N-Queens Solution

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

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

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

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

    backtrack(0);
    return result;
}

console.log(solveNQueens(4));

Solution Approach

Use a recursive backtracking algorithm to explore all valid queen placements.
At each row, try placing a queen in every column and validate its safety.
If placement is valid, proceed to the next row; otherwise, backtrack and try another column.
When all rows are filled, store the valid configuration.

3. Solving Sudoku Puzzle

Example: Basic Backtracking Algorithm for Sudoku

function solveSudoku(board) {
  const emptyCell = findEmptyCell(board);
  if (!emptyCell) return true; // Puzzle solved

  const [row, col] = emptyCell;

  for (let num = 1; num <= 9; num++) {
    if (isValidPlacement(board, row, col, num)) {
      board[row][col] = num;
      if (solveSudoku(board)) return true;
      board[row][col] = 0; // Backtrack
    }
  }

  return false; // No valid number found
}

function findEmptyCell(board) {
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      if (board[i][j] === 0) return [i, j];
    }
  }
  return null;
}

function isValidPlacement(board, row, col, num) {
  // Check row
  for (let i = 0; i < 9; i++) {
    if (board[row][i] === 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;
}

Component	Description	Notes
findEmptyCell	`function(board)`	Finds next empty cell (value 0) in the board
isValidPlacement	`function(board, row, col, num)`	Checks if placing `num` at `(row, col)` is valid
solveSudoku	`function(board)`	Main recursive backtracking function

Note: The algorithm uses a depth-first search approach, trying numbers 1-9 in each empty cell and backtracking when a number leads to an invalid state.

4. Searching Words in Grid

Backtracking is commonly used to search for words in a 2D grid of characters, such as in word search puzzles. The algorithm explores all possible paths from each cell to find a given word.

Property	Description	Example
grid	2D array of characters representing the board	`[['A','B','C'], ['D','E','F'], ['G','H','I']]`
word	String to search for in the grid	`"ABE"`
directions	Array of possible moves (up, down, left, right)	`[[0,1], [1,0], [0,-1], [-1,0]]`

Example: Word Search in Grid

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) return false;
        if (board[row][col] !== word[index]) return false;

        const temp = board[row][col];
        board[row][col] = '#'; // Mark as visited

        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; // Restore
        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;
}

const board = [
    ['A', 'B', 'C'],
    ['D', 'E', 'F'],
    ['G', 'H', 'I']
];
console.log(exist(board, 'ABE')); // true

Note: The algorithm marks visited cells with a temporary character (e.g., '#') to avoid reusing them in the current path, and restores the original character after backtracking.

5. Generating Valid IP Addresses

Example: Generate Valid IP Addresses from String

function restoreIpAddresses(s) {
  const result = [];
  
  function backtrack(start, path) {
    if (path.length === 4 && start === s.length) {
      result.push(path.join("."));
      return;
    }
    
    if (path.length >= 4 || start >= s.length) return;
    
    for (let i = 1; i <= 3 && start + i <= s.length; i++) {
      const segment = s.substring(start, start + i);
      
      if (isValid(segment)) {
        path.push(segment);
        backtrack(start + i, path);
        path.pop();
      }
    }
  }
  
  function isValid(segment) {
    if (segment.length === 0 || segment.length > 3) return false;
    if (segment[0] === "0" && segment.length > 1) return false;
    const num = parseInt(segment);
    return num >= 0 && num <= 255;
  }
  
  backtrack(0, []);
  return result;
}

// Example usage:
console.log(restoreIpAddresses("25525511135"));
// Output: ["255.255.11.135", "255.255.111.35"]

Property	Description	Constraints
Input String	String of digits (0-9)	Length between 1 and 12
Valid IP Segment	Each part must be between 0 and 255	No leading zeros (except for "0" itself)
Number of Segments	Must form exactly 4 segments	Each segment is a valid IP part

Note: Backtracking is used to explore all valid combinations of IP address segments.

Warning: Ensure that each segment is checked for validity before adding to the path.

6. Solving Combination Sum Problems

Problem	Description	Solution Approach	Time Complexity
Combination Sum I	Find all unique combinations in candidates where the candidate numbers sum to target.	Backtracking with recursion, allowing reuse of elements.	O(N^(T/M)) where N is candidates size, T is target, M is min(candidates)
Combination Sum II	Each element can only be used once. Duplicates in candidates are handled.	Backtracking with sorting and skipping duplicates at each level.	O(2^N)
Combination Sum III	Find all valid combinations of k numbers that sum to n, using numbers 1-9 once each.	Backtracking with constraints on count and sum.	O(9^k)

Example: Combination Sum I

function combinationSum(candidates, target) {
    const result = [];
    
    function backtrack(start, currentCombination, remainingTarget) {
        if (remainingTarget === 0) {
            result.push([...currentCombination]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] <= remainingTarget) {
                currentCombination.push(candidates[i]);
                backtrack(i, currentCombination, remainingTarget - candidates[i]);
                currentCombination.pop();
            }
        }
    }
    
    backtrack(0, [], target);
    return result;
}

// Example usage:
const candidates = [2, 3, 6, 7];
const target = 7;
console.log(combinationSum(candidates, target)); 
// Output: [[2,2,3], [7]]

Example: Combination Sum II

function combinationSum2(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];
    
    function backtrack(start, currentCombination, remainingTarget) {
        if (remainingTarget === 0) {
            result.push([...currentCombination]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) continue;
            if (candidates[i] <= remainingTarget) {
                currentCombination.push(candidates[i]);
                backtrack(i + 1, currentCombination, remainingTarget - candidates[i]);
                currentCombination.pop();
            }
        }
    }
    
    backtrack(0, [], target);
    return result;
}

// Example usage:
const candidates = [10, 1, 2, 7, 6, 1, 5];
const target = 8;
console.log(combinationSum2(candidates, target)); 
// Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

Example: Combination Sum III

function combinationSum3(k, n) {
    const result = [];
    
    function backtrack(start, currentCombination, remainingSum, remainingCount) {
        if (remainingCount === 0 && remainingSum === 0) {
            result.push([...currentCombination]);
            return;
        }
        
        if (remainingCount === 0 || remainingSum <= 0) return;
        
        for (let i = start; i <= 9; i++) {
            if (i > remainingSum) break;
            currentCombination.push(i);
            backtrack(i + 1, currentCombination, remainingSum - i, remainingCount - 1);
            currentCombination.pop();
        }
    }
    
    backtrack(1, [], n, k);
    return result;
}

// Example usage:
const k = 3;
const n = 7;
console.log(combinationSum3(k, n)); 
// Output: [[1,2,4]]

Note: For Combination Sum III, the problem constraints ensure that only numbers 1 through 9 are used once each.

7. Solving Palindrome Partitioning

Palindrome Partitioning is a classic backtracking problem where we partition a string such that every substring is a palindrome.

Property	Description	Example
Input	String to be partitioned	`"aab"`
Output	List of all possible palindrome partitions	`[["a","a","b"], ["aa","b"]]`

Example: Palindrome Partitioning

function partition(s) {
    const result = [];
    
    function backtrack(start, path) {
        if (start === s.length) {
            result.push([...path]);
            return;
        }
        
        for (let end = start; end < s.length; end++) {
            const substring = s.slice(start, end + 1);
            if (isPalindrome(substring)) {
                path.push(substring);
                backtrack(end + 1, path);
                path.pop();
            }
        }
    }
    
    function isPalindrome(str) {
        let left = 0;
        let right = str.length - 1;
        while (left < right) {
            if (str[left] !== str[right]) return false;
            left++;
            right--;
        }
        return true;
    }
    
    backtrack(0, []);
    return result;
}

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

Note: The algorithm uses backtracking to explore all possible partitions. For each position, it checks if a substring from that position to the end is a palindrome and recursively processes the remaining string.

8. Generating Phone Letter Combinations

Property	Description	Example
Input	String of digits (2-9)	`"23"`
Output	All possible letter combinations	`["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]`

Example: Phone Letter Combinations

function letterCombinations(digits) {
  if (digits.length === 0) return [];
  
  const mapping = {
    "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 = mapping[digits[index]];
    for (let letter of letters) {
      backtrack(index + 1, current + letter);
    }
  }

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

console.log(letterCombinations("23"));

Note: This backtracking approach explores all combinations by building one character at a time and recursively trying each letter for the next digit.

9. Solving Rat in Maze Problem

The Rat in Maze problem is a classic backtracking challenge where we need to find a path from the top-left corner to the bottom-right corner of a maze, where 1 represents a valid path and 0 represents a blocked cell.

Property	Description	Values
maze	2D array representing the maze	`[[1, 0, 1, 1], [1, 1, 1, 0], [0, 1, 1, 1]]`
solution	2D array storing the path	`[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]`

Example: Solving Rat in Maze

function solveMaze(maze) {
  const n = maze.length;
  const solution = Array(n).fill().map(() => Array(n).fill(0));

  function isSafe(x, y) {
    return x >= 0 && y >= 0 && x < n && y < n && maze[x][y] === 1;
  }

  function solveUtil(x, y) {
    if (x === n - 1 && y === n - 1) {
      solution[x][y] = 1;
      return true;
    }

    if (isSafe(x, y)) {
      solution[x][y] = 1;

      if (solveUtil(x + 1, y)) return true;
      if (solveUtil(x, y + 1)) return true;

      solution[x][y] = 0;
      return false;
    }

    return false;
  }

  if (solveUtil(0, 0)) {
    return solution;
  }
  return null;
}

const maze = [
  [1, 0, 1, 1],
  [1, 1, 1, 0],
  [0, 1, 1, 1],
  [1, 1, 0, 1]
];

console.log(solveMaze(maze));

Note: The solution matrix shows the path taken to reach the destination. If no path exists, it returns null.

10. Solving Knight's Tour Problem

The Knight's Tour problem involves finding a sequence of moves for a knight on a chessboard such that the knight visits every square exactly once. This is a classic application of backtracking.

Property	Description	Notes
Board Size	Standard chessboard is 8x8, but can vary	Requires a grid of size n×n
Knight Moves	8 possible moves from any position	Each move is 2 squares in one direction and 1 in perpendicular
Solution Type	Hamiltonian Path	Visits each square once, does not return to start

Example: Knight's Tour Implementation

function solveKnightTour(n) {
  const board = Array(n).fill().map(() => Array(n).fill(0));
  const moves = [[2,1], [1,2], [-1,2], [-2,1], [-2,-1], [-1,-2], [1,-2], [2,-1]];
  
  function isSafe(x, y) {
    return x >= 0 && x < n && y >= 0 && y < n && board[x][y] === 0;
  }
  
  function solve(x, y, move) {
    if (move === n * n) return true;
    
    for (const [dx, dy] of moves) {
      const newX = x + dx;
      const newY = y + dy;
      if (isSafe(newX, newY)) {
        board[newX][newY] = move + 1;
        if (solve(newX, newY, move + 1)) return true;
        board[newX][newY] = 0;
      }
    }
    return false;
  }
  
  board[0][0] = 1;
  if (solve(0, 0, 1)) {
    return board;
  }
  return null;
}

Note: The backtracking approach systematically explores all valid knight moves, and if a path leads to a dead end, it backtracks to try another move.

11. Solving Expression Add Operators

Solves the problem of inserting +, -, or * operators between digits of a string to form valid expressions that evaluate to a target value.

Property	Description	Example
Input	String of digits and target integer	`"123"`, `6`
Operators	Allowed operators: `+`, `-`, `*`	None
Output	List of valid expressions that evaluate to target	`["1+2+3", "123"]`

Example: Expression Add Operators

function addOperators(num, target) {
    const result = [];
    
    function backtrack(start, path, value, prev) {
        if (start === num.length) {
            if (value === target) {
                result.push(path);
            }
            return;
        }
        
        for (let i = start; i < num.length; i++) {
            const current = num.substring(start, i + 1);
            const currentNum = parseInt(current);
            
            if (start === 0) {
                backtrack(i + 1, current, currentNum, currentNum);
            } else {
                backtrack(i + 1, path + '+' + current, value + currentNum, currentNum);
                backtrack(i + 1, path + '-' + current, value - currentNum, -currentNum);
                backtrack(i + 1, path + '*' + current, value - prev + prev * currentNum, prev * currentNum);
            }
            
            if (current[0] === '0' && current.length > 1) break;
        }
    }
    
    backtrack(0, '', 0, 0);
    return result;
}

// Example usage:
console.log(addOperators("123", 6)); // ["1+2+3", "1*2*3"]

Note: Backtracking is used to explore all possible operator combinations. The prev parameter helps handle operator precedence correctly for multiplication.

12. Restoring IP Addresses

Given a string containing only digits, return all possible valid IP address combinations that can be formed by inserting dots.

Input	Output	Description
s = "25525511135"	`["255.255.11.135", "255.255.111.35"]`	Valid IP addresses formed from the string

Example: Valid IP Address Combinations

function restoreIpAddresses(s) {
    const result = [];
    
    function backtrack(start, path) {
        if (path.length === 4 && start === s.length) {
            result.push(path.join('.'));
            return;
        }
        
        if (path.length >= 4 || start >= s.length) return;
        
        for (let i = 1; i <= 3; i++) {
            const segment = s.substring(start, start + i);
            
            if (isValid(segment)) {
                path.push(segment);
                backtrack(start + i, path);
                path.pop();
            }
        }
    }
    
    function isValid(segment) {
        if (segment.length === 0 || segment.length > 3) return false;
        if (segment[0] === '0' && segment.length > 1) return false;
        return parseInt(segment) <= 255;
    }
    
    backtrack(0, []);
    return result;
}

// Example usage:
console.log(restoreIpAddresses("25525511135"));
// Output: ["255.255.11.135", "255.255.111.35"]

Note: Each segment of the IP address must be between 0 and 255, and cannot have leading zeros unless it's exactly "0".