Backtracking Pattern

1. Generate All Subsets (Powerset)

Approach	Mechanism	Complexity	Advantage
Backtracking Recursive	Include/exclude each element	`O(2^n * n)`	Natural, easy to understand
Bit Manipulation	Each bit represents inclusion	`O(2^n * n)`	Iterative, no recursion stack
Total Subsets	2^n subsets for n elements	Powerset size	Each element: in or out
Iterative Building	Add each element to existing subsets	`O(2^n * n)`	Simple iteration pattern

Example: Subsets using backtracking

function subsets(nums) {
    const result = [];
    const current = [];
    
    function backtrack(index) {
        // Add current subset to result
        result.push([...current]);
        
        // Try adding each remaining element
        for (let i = index; i < nums.length; i++) {
            current.push(nums[i]);
            backtrack(i + 1);
            current.pop(); // Backtrack
        }
    }
    
    backtrack(0);
    return result;
}

// [1,2,3] -> [[],[1],[1,2],[1,2,3],
//              [1,3],[2],[2,3],[3]]
// Time: O(2^n * n), Space: O(n) recursion

Example: Subsets using bit manipulation

function subsetsBitManipulation(nums) {
    const n = nums.length;
    const totalSubsets = 1 << n; // 2^n
    const result = [];
    
    for (let mask = 0; mask < totalSubsets; mask++) {
        const subset = [];
        
        for (let i = 0; i < n; i++) {
            // Check if i-th bit is set
            if (mask & (1 << i)) {
                subset.push(nums[i]);
            }
        }
        
        result.push(subset);
    }
    
    return result;
}

// [1,2,3] -> same result
// No recursion, iterative approach

Example: Subsets with duplicates

function subsetsWithDup(nums) {
    nums.sort((a, b) => a - b); // Sort to group duplicates
    const result = [];
    const current = [];
    
    function backtrack(index) {
        result.push([...current]);
        
        for (let i = index; i < nums.length; i++) {
            // Skip duplicates at same level
            if (i > index && nums[i] === nums[i - 1]) {
                continue;
            }
            
            current.push(nums[i]);
            backtrack(i + 1);
            current.pop();
        }
    }
    
    backtrack(0);
    return result;
}

// [1,2,2] -> [[],[1],[1,2],[1,2,2],[2],[2,2]]
// Avoids duplicate subsets like [1,2] appearing twice

2. Permutations and Next Lexicographic Order

Method	Strategy	Complexity	Use Case
Backtracking Swap	Swap elements, recurse, backtrack	`O(n! * n)`	Generate all permutations
Next Permutation Algorithm	Find pivot, swap, reverse suffix	`O(n)` per permutation	Lexicographic ordering
Used Array Tracking	Boolean array to mark used elements	`O(n)` extra space	Clearer logic, handles duplicates
Total Permutations	n! permutations for n distinct elements	Factorial growth	Combinatorial explosion

Example: Permutations using backtracking

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]);
            
            // Create new remaining array without i-th element
            const newRemaining = [
                ...remaining.slice(0, i),
                ...remaining.slice(i + 1)
            ];
            
            backtrack(current, newRemaining);
            current.pop();
        }
    }
    
    backtrack([], nums);
    return result;
}

// [1,2,3] -> [[1,2,3],[1,3,2],
//              [2,1,3],[2,3,1],
//              [3,1,2],[3,2,1]]

Example: Permutations with swap

function permuteSwap(nums) {
    const result = [];
    
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        
        for (let i = start; i < nums.length; i++) {
            // Swap current with start
            [nums[start], nums[i]] = 
                [nums[i], nums[start]];
            
            backtrack(start + 1);
            
            // Backtrack: swap back
            [nums[start], nums[i]] = 
                [nums[i], nums[start]];
        }
    }
    
    backtrack(0);
    return result;
}

// More efficient - O(1) space

Example: Next lexicographic permutation

function nextPermutation(nums) {
    // Step 1: Find rightmost pair where nums[i] < nums[i+1]
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    
    if (i >= 0) {
        // Step 2: Find rightmost element greater than nums[i]
        let j = nums.length - 1;
        while (j >= 0 && nums[j] <= nums[i]) {
            j--;
        }
        
        // Step 3: Swap
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    
    // Step 4: Reverse suffix from i+1 to end
    let left = i + 1;
    let right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
    
    return nums; // Modified in-place
}

// [1,2,3] -> [1,3,2]
// [3,2,1] -> [1,2,3] (wraps around)
// Time: O(n), Space: O(1)

3. N-Queens Problem Solution

Constraint	Check Method	Optimization	Data Structure
No Same Row	Place one queen per row	Implicit - iterate row by row	Guaranteed by iteration
No Same Column	Track used columns with set/array	O(1) lookup with set	`Set` or boolean array
No Same Diagonal	Track diagonals: row-col and row+col	O(1) lookup with sets	Two sets for both diagonals
Backtracking	Try each column, recurse, undo	Early pruning on conflicts	`O(n!)` time complexity

Example: N-Queens solution

function solveNQueens(n) {
    const result = [];
    const board = Array(n).fill(null).map(() => Array(n).fill('.'));
    const cols = new Set();
    const diag1 = new Set(); // row - col
    const diag2 = new Set(); // row + col
    
    function backtrack(row) {
        if (row === n) {
            // Found valid solution
            result.push(board.map(r => r.join('')));
            return;
        }
        
        for (let col = 0; col < n; col++) {
            // Check if position is safe
            if (cols.has(col) || 
                diag1.has(row - col) || 
                diag2.has(row + col)) {
                continue;
            }
            
            // Place queen
            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            
            backtrack(row + 1);
            
            // Backtrack
            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }
    
    backtrack(0);
    return result;
}

// n=4 -> [[".Q..","...Q","Q...","..Q."],
//          ["..Q.","Q...","...Q",".Q.."]]
// Time: O(n!), Space: O(n)

Example: N-Queens count only

function totalNQueens(n) {
    let count = 0;
    const cols = new Set();
    const diag1 = new Set();
    const diag2 = new Set();
    
    function backtrack(row) {
        if (row === n) {
            count++;
            return;
        }
        
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || 
                diag1.has(row - col) || 
                diag2.has(row + col)) {
                continue;
            }
            
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            
            backtrack(row + 1);
            
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }
    
    backtrack(0);
    return count;
}

// More efficient - no board construction

4. Sudoku Solver Backtracking

Technique	Description	Impact	Complexity
Constraint Checking	Row, column, 3x3 box validation	Prune invalid choices early	O(1) with precomputed sets
Most Constrained First	Fill cells with fewest options first	Reduces branching factor	Heuristic optimization
Naked Singles	Cells with only one valid option	Deterministic placement	Preprocessing step
Backtracking	Try 1-9, recurse, undo on conflict	Exhaustive search with pruning	Worst case exponential

Example: Sudoku solver

function solveSudoku(board) {
    function isValid(board, row, col, num) {
        // Check row
        for (let c = 0; c < 9; c++) {
            if (board[row][c] === num) return false;
        }
        
        // Check column
        for (let r = 0; r < 9; r++) {
            if (board[r][col] === num) return false;
        }
        
        // Check 3x3 box
        const boxRow = Math.floor(row / 3) * 3;
        const boxCol = Math.floor(col / 3) * 3;
        for (let r = boxRow; r < boxRow + 3; r++) {
            for (let c = boxCol; c < boxCol + 3; c++) {
                if (board[r][c] === 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(board, row, col, char)) {
                            board[row][col] = char;
                            
                            if (backtrack()) {
                                return true;
                            }
                            
                            board[row][col] = '.'; // Backtrack
                        }
                    }
                    
                    return false; // No valid number found
                }
            }
        }
        
        return true; // Board complete
    }
    
    backtrack();
    return board;
}

// Modifies board in-place
// Time: O(9^m) where m = empty cells

5. Combination Sum Problem

Variant	Rule	Strategy	Optimization
Unlimited Reuse	Same element can be used multiple times	Don't increment index after use	Sort array, prune when exceeds target
Use Once	Each element used at most once	Increment index after use	Skip duplicates at same level
Fixed Length K	Combination must have exactly K elements	Track combination size	Prune when size exceeds K
Early Pruning	Stop when current sum > target	Requires sorted array	Dramatically reduces branches

Example: Combination sum (unlimited reuse)

function combinationSum(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);
    
    function backtrack(start, current, sum) {
        if (sum === target) {
            result.push([...current]);
            return;
        }
        
        if (sum > target) return; // Prune
        
        for (let i = start; i < candidates.length; i++) {
            // Prune: no point continuing if exceeds
            if (sum + candidates[i] > target) break;
            
            current.push(candidates[i]);
            // Can reuse same element: start at i
            backtrack(i, current, sum + candidates[i]);
            current.pop();
        }
    }
    
    backtrack(0, [], 0);
    return result;
}

// [2,3,6,7], target=7
// -> [[2,2,3],[7]]

Example: Combination sum II (use once)

function combinationSum2(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);
    
    function backtrack(start, current, sum) {
        if (sum === target) {
            result.push([...current]);
            return;
        }
        
        if (sum > target) return;
        
        for (let i = start; i < candidates.length; i++) {
            // Skip duplicates at same level
            if (i > start && 
                candidates[i] === candidates[i - 1]) {
                continue;
            }
            
            if (sum + candidates[i] > target) break;
            
            current.push(candidates[i]);
            // Use once: start at i+1
            backtrack(i + 1, current, 
                     sum + candidates[i]);
            current.pop();
        }
    }
    
    backtrack(0, [], 0);
    return result;
}

// [10,1,2,7,6,1,5], target=8
// -> [[1,1,6],[1,2,5],[1,7],[2,6]]

6. Word Search in 2D Grid (DFS Backtracking)

Component	Implementation	Purpose	Optimization
DFS from Each Cell	Try starting from every position	Find word starting point	Early exit on first match found
Path Tracking	Mark visited cells during DFS	Avoid revisiting in same path	Backtrack by unmarking
4-directional Search	Explore up, down, left, right	Find adjacent matching characters	Bounds checking required
Character Matching	Match current character with word[index]	Validate path correctness	Mismatch = immediate backtrack

Example: Word search in grid

function exist(board, word) {
    const rows = board.length;
    const cols = board[0].length;
    
    function dfs(row, col, index) {
        // Found complete word
        if (index === word.length) return true;
        
        // Out of bounds or mismatch
        if (row < 0 || row >= rows || 
            col < 0 || col >= cols ||
            board[row][col] !== word[index]) {
            return false;
        }
        
        // Mark as visited
        const temp = board[row][col];
        board[row][col] = '#';
        
        // Explore all 4 directions
        const found = 
            dfs(row + 1, col, index + 1) ||
            dfs(row - 1, col, index + 1) ||
            dfs(row, col + 1, index + 1) ||
            dfs(row, col - 1, index + 1);
        
        // Backtrack
        board[row][col] = temp;
        
        return found;
    }
    
    // Try starting from each cell
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    
    return false;
}

// board = [["A","B","C","E"],
//          ["S","F","C","S"],
//          ["A","D","E","E"]]
// word = "ABCCED" -> true
// Time: O(m*n*4^L) where L=word length

Example: Word search II (multiple words with Trie)

class TrieNode {
    constructor() {
        this.children = {};
        this.word = null;
    }
}

function findWords(board, words) {
    // Build Trie
    const root = new TrieNode();
    for (const word of words) {
        let node = root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.word = word;
    }
    
    const result = [];
    const rows = board.length;
    const cols = board[0].length;
    
    function dfs(row, col, node) {
        const char = board[row][col];
        if (char === '#' || !node.children[char]) return;
        
        node = node.children[char];
        
        if (node.word) {
            result.push(node.word);
            node.word = null; // Avoid duplicates
        }
        
        board[row][col] = '#';
        
        if (row > 0) dfs(row - 1, col, node);
        if (row < rows - 1) dfs(row + 1, col, node);
        if (col > 0) dfs(row, col - 1, node);
        if (col < cols - 1) dfs(row, col + 1, node);
        
        board[row][col] = char;
    }
    
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            dfs(r, c, root);
        }
    }
    
    return result;
}

// More efficient for multiple words

7. Palindrome Partitioning Problem

Concept	Strategy	Optimization	Complexity
Partition Points	Try splitting at every position	Only split if prefix is palindrome	O(n) palindrome check per split
Backtracking	Build partition, recurse, backtrack	Exponential search space	O(2^n) partitions possible
DP Palindrome Check	Precompute all palindrome substrings	O(1) palindrome lookup	O(n²) preprocessing time/space
Expand Around Center	Check palindrome by expanding outward	O(n) per check, no extra space	Trade-off: time vs space

Example: Palindrome partitioning

function partition(s) {
    const result = [];
    
    function isPalindrome(str, left, right) {
        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; end < s.length; end++) {
            // Only proceed if substring is palindrome
            if (isPalindrome(s, start, end)) {
                current.push(s.substring(start, end + 1));
                backtrack(end + 1, current);
                current.pop();
            }
        }
    }
    
    backtrack(0, []);
    return result;
}

// "aab" -> [["a","a","b"],["aa","b"]]
// "a" -> [["a"]]
// Time: O(n * 2^n), Space: O(n)

Example: Palindrome partitioning with DP optimization

function partitionDP(s) {
    const n = s.length;
    // DP table: dp[i][j] = true if s[i..j] is palindrome
    const dp = Array(n).fill(null).map(() => Array(n).fill(false));
    
    // Precompute all palindromes
    for (let len = 1; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            if (len === 1) {
                dp[i][j] = true;
            } else if (len === 2) {
                dp[i][j] = s[i] === s[j];
            } else {
                dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
            }
        }
    }
    
    const result = [];
    
    function backtrack(start, current) {
        if (start === n) {
            result.push([...current]);
            return;
        }
        
        for (let end = start; end < n; end++) {
            // O(1) palindrome check
            if (dp[start][end]) {
                current.push(s.substring(start, end + 1));
                backtrack(end + 1, current);
                current.pop();
            }
        }
    }
    
    backtrack(0, []);
    return result;
}

// Faster palindrome checks: O(1) instead of O(n)
// Trade-off: O(n²) space for DP table

Backtracking Pattern Summary

Core Pattern: Choose → Explore → Unchoose (backtrack)
Subsets: Include/exclude decision tree, 2^n total subsets
Permutations: Swap-based or used-array approach, n! permutations
N-Queens: Constraint propagation with sets for O(1) conflict detection
Sudoku: Try 1-9, validate constraints, backtrack on conflict
Combination Sum: Sort array, prune when sum exceeds target
Word Search: DFS with visited marking, 4-directional exploration
Palindrome Partition: Try all splits, verify palindrome, recurse

Note: Backtracking is exhaustive search with pruning. Key optimizations: (1) Early termination when constraints violated, (2) Sort data for pruning opportunities, (3) Precompute expensive checks (like palindrome DP table), (4) Track state efficiently (sets for O(1) lookup vs arrays).

Warning: Backtracking has exponential time complexity in worst case. Always implement pruning strategies to reduce search space. For Sudoku/N-Queens, use sets for O(1) constraint checking instead of O(n) scans. Remember to backtrack properly - undo all state changes when returning from recursion.

Related Cheat Sheets

Datastructures Algorithms