--- # === IDENTITY === id: software/patterns/backtracking-patterns/2026 canonical_question: "What are the common backtracking patterns?" aliases: - "backtracking algorithm template" - "recursive backtracking choose explore unchoose" - "backtracking permutations combinations subsets" - "N-Queens Sudoku backtracking solution" - "constraint satisfaction backtracking" - "backtracking pruning strategies" entity_type: software_reference domain: software > patterns > backtracking_patterns region: global jurisdiction: global temporal_scope: 1960-2026 # === VERIFICATION === last_verified: 2026-02-24 confidence: 0.95 version: 1.0 first_published: 2026-02-24 # === TEMPORAL VALIDITY === temporal_validity: status: stable last_breaking_change: null next_review: 2026-08-23 change_sensitivity: low # === CONSTRAINTS === constraints: - "Backtracking has worst-case exponential time O(b^d) where b is branching factor and d is depth; always estimate feasibility before implementing" - "State must be fully restored after each recursive call (choose-explore-unchoose); partial undo causes silent corruption of later branches" - "Pruning is not optional for production use; unpruned backtracking on N-Queens with N>12 or Sudoku with many blanks is computationally infeasible" - "Base case must terminate recursion; missing or incorrect base case causes infinite recursion / stack overflow" - "Mutable shared state (arrays, sets) must be passed by reference and restored, not copied, to avoid O(n!) space blowup" # === SKIP CONDITIONS === skip_this_unit_if: - condition: "Problem has overlapping subproblems and optimal substructure (counting or optimization, not enumeration)" use_instead: "Use dynamic programming instead of backtracking" - condition: "Need shortest path or minimum steps in unweighted state space" use_instead: "Use BFS (breadth-first search) for shortest-path problems" - condition: "Greedy choice property holds and locally optimal choices lead to global optimum" use_instead: "Use greedy algorithm for provably greedy-safe problems" # === AGENT HINTS === inputs_needed: - key: problem_type question: "What type of backtracking problem are you solving?" type: choice options: ["permutations", "combinations", "subsets", "constraint satisfaction (N-Queens, Sudoku)", "board/grid search (word search)", "partitioning (palindrome partitioning)"] - key: language question: "Which programming language?" type: choice options: ["Python", "JavaScript", "Java", "C++", "Go"] - key: duplicates question: "Can the input contain duplicate elements?" type: choice options: ["no duplicates", "has duplicates (need dedup)"] # === DISTRIBUTION === canonical_source: "https://knowledgelib.io/software/patterns/backtracking-patterns/2026" suggested_citation: "Source: knowledgelib.io -- AI Knowledge Library (verified 2026-02-24)" # === RELATED UNITS === related_kos: depends_on: [] related_to: - id: "software/patterns/dynamic-programming/2026" label: "Dynamic Programming Patterns" - id: "software/patterns/graph-algorithms/2026" label: "Graph Algorithm Patterns" - id: "software/patterns/binary-search-variations/2026" label: "Binary Search Variations" solves: [] alternative_to: [] often_confused_with: - id: "software/patterns/dynamic-programming/2026" label: "Dynamic Programming (overlapping subproblems, not enumeration)" # === SOURCES (7 authoritative sources) === sources: - id: src1 title: "Backtracking Algorithm Common Patterns and Code Template" author: labuladong url: https://labuladong.online/en/algo/essential-technique/backtrack-framework/ type: technical_blog published: 2024-01-15 reliability: high - id: src2 title: "A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning)" author: LeetCode Community url: https://leetcode.com/problems/combination-sum/solutions/16502/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partitioning)/ type: community_resource published: 2015-05-19 reliability: high - id: src3 title: "Introduction to Backtracking" author: GeeksforGeeks url: https://www.geeksforgeeks.org/dsa/introduction-to-backtracking-2/ type: technical_blog published: 2024-12-18 reliability: moderate_high - id: src4 title: "Coding Interview Backtracking Problems Crash Course" author: freeCodeCamp url: https://www.freecodecamp.org/news/coding-interview-backtracking-problems-crash-course/ type: technical_blog published: 2024-06-10 reliability: moderate_high - id: src5 title: "Recursive Backtracking Algorithm" author: AlgoMap url: https://algomap.io/lessons/recursive-backtracking type: technical_blog published: 2025-01-10 reliability: moderate_high - id: src6 title: "Backtracking Introduction" author: AlgoMaster.io url: https://algomaster.io/learn/dsa/backtracking-introduction type: technical_blog published: 2025-03-15 reliability: moderate_high - id: src7 title: "Backtracking Algorithms: N-Queens, Sudoku & Subset Sum" author: Mbloging url: https://www.mbloging.com/post/backtracking-algorithms-n-queens-sudoku-subset-sum type: technical_blog published: 2025-06-12 reliability: moderate --- # Common Backtracking Patterns ## TL;DR - **Bottom line**: Backtracking systematically explores all candidate solutions via recursive choose-explore-unchoose, pruning invalid branches early to avoid full exponential search. - **Key tool**: The recursive `backtrack(path, choices)` template with state restoration after each recursive call. - **Watch out for**: Forgetting to undo state changes after recursion (the "unchoose" step), which silently corrupts remaining branches. - **Works with**: Any language with recursion; patterns are language-agnostic. Most commonly implemented in Python, Java, JavaScript, and C++. ## Constraints - Backtracking has worst-case exponential time O(b^d); always estimate feasibility before implementing - State must be fully restored after each recursive call; partial undo causes silent corruption of later branches - Pruning is not optional for production use; unpruned backtracking is computationally infeasible for non-trivial inputs - Base case must terminate recursion; missing or incorrect base case causes infinite recursion / stack overflow - Mutable shared state (arrays, sets) must be passed by reference and restored, not copied per call, to avoid O(n!) space blowup ## Quick Reference | Pattern | Time Complexity | Space Complexity | Pruning Strategy | Classic Problems | |---|---|---|---|---| | Permutations (no dups) | O(n! * n) | O(n) | Skip used elements via `visited[]` | Permutations (LC 46) | | Permutations (with dups) | O(n! * n) | O(n) | Sort + skip `nums[i] == nums[i-1]` if prev unused | Permutations II (LC 47) | | Combinations | O(C(n,k) * k) | O(k) | Start index prevents revisiting; prune if remaining < needed | Combinations (LC 77) | | Combination Sum (reuse) | O(n^(t/min)) | O(t/min) | Skip candidates > remaining target | Combination Sum (LC 39) | | Combination Sum (no reuse) | O(2^n * n) | O(n) | Sort + skip duplicates + start index | Combination Sum II (LC 40) | | Subsets (no dups) | O(2^n * n) | O(n) | Start index; collect at every node | Subsets (LC 78) | | Subsets (with dups) | O(2^n * n) | O(n) | Sort + skip `nums[i] == nums[i-1]` | Subsets II (LC 90) | | N-Queens | O(n!) | O(n) | Column, diagonal, anti-diagonal sets | N-Queens (LC 51) | | Sudoku Solver | O(9^m) where m = blanks | O(m) | Row/col/box constraint sets | Sudoku Solver (LC 37) | | Word Search (grid) | O(m*n * 4^L) | O(L) | Bounds check + visited cell marking | Word Search (LC 79) | | Palindrome Partitioning | O(n * 2^n) | O(n) | Prune non-palindrome prefixes early | Palindrome Partitioning (LC 131) | ## Decision Tree ``` START: Do you need to enumerate ALL valid solutions (not just count or optimize)? ├── YES: Is there a constraint that eliminates large branches early? │ ├── YES → Backtracking with pruning (this unit) │ └── NO → Backtracking still works but may be slow; consider if problem size allows exponential time ├── NO: Do subproblems overlap (same state reachable via different paths)? │ ├── YES → Dynamic Programming │ └── NO ↓ ├── Need shortest path / minimum steps in state space? │ ├── YES → BFS (breadth-first search) │ └── NO ↓ ├── Can you prove greedy choice property? │ ├── YES → Greedy algorithm │ └── NO ↓ └── DEFAULT → Backtracking with pruning is the safe fallback for constraint satisfaction ``` ## Step-by-Step Guide ### 1. Identify the backtracking structure Determine what constitutes a "choice" at each step, what the "path" (partial solution) looks like, and when you've reached a complete solution (base case). Draw the decision tree on paper first. [src1] ``` Three key concepts: - PATH: choices already made (the partial solution so far) - CHOICES: options available at the current step - BASE: condition where path is a complete valid solution ``` **Verify**: Can you draw a tree where each level represents one choice? If yes, backtracking applies. ### 2. Write the general template Every backtracking solution follows this skeleton. Customize the three marked sections. [src1] ```python def backtrack(path, choices): if is_complete(path): # BASE CASE result.append(path[:]) # save a copy return for choice in choices: if not is_valid(choice): # PRUNE continue path.append(choice) # CHOOSE backtrack(path, next_choices) # EXPLORE path.pop() # UNCHOOSE (undo) ``` **Verify**: Confirm that every `append` has a matching `pop`, and the base case copies the path (not references it). ### 3. Add pruning to reduce search space Without pruning, you explore every branch. Add constraints that skip invalid choices before recursing. [src3] ```python # Example: combination sum — prune when remaining target < 0 def backtrack(path, start, remaining): if remaining == 0: result.append(path[:]) return for i in range(start, len(candidates)): if candidates[i] > remaining: # PRUNE: sorted, so all after are too large break path.append(candidates[i]) backtrack(path, i, remaining - candidates[i]) path.pop() ``` **Verify**: Sort input first when using comparison-based pruning. Time reduction from O(2^n) to practical feasibility. ### 4. Handle duplicates (when input has repeated elements) Sort the input, then skip consecutive duplicates at the same decision level. [src2] ```python # Skip duplicates: if nums[i] == nums[i-1] and i > start, skip candidates.sort() for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i - 1]: continue # skip duplicate at same level # ... choose, explore, unchoose ``` **Verify**: Output should contain no duplicate subsets/combinations. Test with input like `[1, 1, 2]`. ## Code Examples ### Python: Subsets (Power Set) ```python # Input: nums = [1, 2, 3] # Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] def subsets(nums): result = [] def backtrack(start, path): result.append(path[:]) # collect at every node for i in range(start, len(nums)): path.append(nums[i]) # choose backtrack(i + 1, path) # explore (i+1 prevents reuse) path.pop() # unchoose backtrack(0, []) return result ``` ### Python: N-Queens ```python # Input: n = 4 # Output: all valid board configurations as lists of queen positions def solve_n_queens(n): result, cols, diags, anti = [], set(), set(), set() def backtrack(row, queens): if row == n: result.append(queens[:]) return for col in range(n): if col in cols or (row-col) in diags or (row+col) in anti: continue # prune: conflict detected cols.add(col); diags.add(row-col); anti.add(row+col) backtrack(row + 1, queens + [col]) cols.remove(col); diags.remove(row-col); anti.remove(row+col) backtrack(0, []) return result ``` ### JavaScript: Permutations ```javascript // Input: nums = [1, 2, 3] // Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] function permute(nums) { const result = []; function backtrack(path, used) { if (path.length === nums.length) { result.push([...path]); return; } for (let i = 0; i < nums.length; i++) { if (used[i]) continue; // skip already-used elements used[i] = true; path.push(nums[i]); // choose backtrack(path, used); // explore path.pop(); used[i] = false; // unchoose } } backtrack([], new Array(nums.length).fill(false)); return result; } ``` ### JavaScript: Combination Sum ```javascript // Input: candidates = [2,3,6,7], target = 7 // Output: [[2,2,3],[7]] function combinationSum(candidates, target) { candidates.sort((a, b) => a - b); const result = []; function backtrack(start, path, remaining) { if (remaining === 0) { result.push([...path]); return; } for (let i = start; i < candidates.length; i++) { if (candidates[i] > remaining) break; // prune path.push(candidates[i]); backtrack(i, path, remaining - candidates[i]); // i, not i+1 (reuse) path.pop(); } } backtrack(0, [], target); return result; } ``` ### Java: Sudoku Solver Full script: [SudokuSolver.java](scripts/SudokuSolver.java) (45 lines) ```java // Input: 9x9 board with '.' for empty cells // Output: solved board in-place public void solveSudoku(char[][] board) { solve(board); } private boolean solve(char[][] board) { for (int r = 0; r < 9; r++) for (int c = 0; c < 9; c++) if (board[r][c] == '.') { for (char d = '1'; d <= '9'; d++) { if (isValid(board, r, c, d)) { board[r][c] = d; // choose if (solve(board)) return true; // explore board[r][c] = '.'; // unchoose } } return false; // no valid digit: trigger backtrack } return true; // all cells filled } ``` ### Java: Palindrome Partitioning ```java // Input: s = "aab" // Output: [["a","a","b"],["aa","b"]] public List> partition(String s) { List> result = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), result); return result; } void backtrack(String s, int start, List path, List> result) { if (start == s.length()) { result.add(new ArrayList<>(path)); return; } for (int end = start + 1; end <= s.length(); end++) { String sub = s.substring(start, end); if (!isPalindrome(sub)) continue; // prune non-palindromes path.add(sub); backtrack(s, end, path, result); path.remove(path.size() - 1); } } ``` ## Anti-Patterns ### Wrong: Forgetting to undo state changes ```python # BAD -- missing path.pop() after recursion def backtrack(path, start): result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) backtrack(path, i + 1) # forgot path.pop() -- path grows forever, all results are wrong ``` ### Correct: Always undo after recursion ```python # GOOD -- symmetric choose/unchoose def backtrack(path, start): result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) # choose backtrack(path, i + 1) # explore path.pop() # unchoose -- MUST match the append ``` ### Wrong: Storing reference instead of copy ```python # BAD -- appending the same list object, not a snapshot def backtrack(path, start): if len(path) == k: result.append(path) # all entries point to same list! return ``` ### Correct: Copy the path before storing ```python # GOOD -- append a shallow copy def backtrack(path, start): if len(path) == k: result.append(path[:]) # path[:] or list(path) creates a copy return ``` ### Wrong: No pruning on sorted candidates ```python # BAD -- tries every candidate even when sum already exceeds target for i in range(start, len(candidates)): path.append(candidates[i]) backtrack(path, i, remaining - candidates[i]) path.pop() ``` ### Correct: Break early when candidate exceeds remaining ```python # GOOD -- sort candidates first, then break when too large candidates.sort() for i in range(start, len(candidates)): if candidates[i] > remaining: break # all subsequent candidates are also too large path.append(candidates[i]) backtrack(path, i, remaining - candidates[i]) path.pop() ``` ### Wrong: Not handling duplicates at same decision level ```python # BAD -- produces duplicate subsets for input [1, 1, 2] for i in range(start, len(nums)): path.append(nums[i]) backtrack(path, i + 1) path.pop() ``` ### Correct: Skip duplicates at same level after sorting ```python # GOOD -- skip nums[i] if it equals nums[i-1] at the same decision level nums.sort() for i in range(start, len(nums)): if i > start and nums[i] == nums[i - 1]: continue # skip duplicate at same tree level path.append(nums[i]) backtrack(path, i + 1) path.pop() ``` ## Common Pitfalls - **Stack overflow on deep recursion**: Python default recursion limit is 1000. For deep backtracking (e.g., Sudoku with many blanks), either increase with `sys.setrecursionlimit()` or convert to iterative with an explicit stack. [src3] - **O(n!) space from copying path at every node**: Copying the path at every recursive call instead of only at leaf/base-case nodes wastes memory. Only copy when you add to `result`. Fix: move `result.append(path[:])` inside the base case check. [src1] - **Using `start` parameter for permutations**: Permutations need a `used[]` boolean array (or swap-based approach), not a `start` index. Using `start` produces combinations, not permutations. Fix: use `visited[i]` to track which elements are already in the path. [src2] - **Mutating the choices list during iteration**: Removing/adding elements to the candidates array while iterating over it causes skipped or duplicated elements. Fix: use index-based iteration and `start` parameter instead of modifying the list. [src4] - **Incorrect diagonal check in N-Queens**: Using `abs(row1-row2) == abs(col1-col2)` with O(n) scan per placement. Fix: use three sets (`cols`, `diags`, `anti_diags`) for O(1) conflict detection. [src7] - **Not sorting before duplicate skipping**: The `nums[i] == nums[i-1]` skip logic only works on sorted input. Applying it to unsorted input either misses duplicates or incorrectly skips valid choices. Fix: always `sort()` first. [src2] ## When to Use / When Not to Use | Use When | Don't Use When | Use Instead | |---|---|---| | Need ALL valid solutions (enumerate every permutation, combination, subset) | Need only the COUNT of solutions | Dynamic Programming | | Constraint satisfaction problems (N-Queens, Sudoku, crossword) | Problem has overlapping subproblems with optimal substructure | Dynamic Programming (memoization) | | Search space can be pruned significantly by constraints | Need shortest path or minimum steps | BFS (breadth-first search) | | Decision tree is finite and bounded | Greedy choice property is provable | Greedy algorithm | | Input size is small enough for exponential time (n <= ~20 for subsets, n <= ~10 for permutations) | Input size is large (n > 25 for subsets) | DP, math formulas, or meet-in-the-middle | | Need to generate actual solutions, not just existence/count | State space is infinite or unbounded | Iterative deepening or bounded search | | Grid/board puzzles with local constraints (word search, maze) | Graph has no dead ends to prune | DFS without backtracking suffices | ## Important Caveats - Backtracking is fundamentally exponential; no amount of pruning changes the worst case. For n > 20-25 (subsets/combinations) or n > 10-12 (permutations), consider whether the problem truly requires full enumeration. - The choose-explore-unchoose pattern assumes mutable state. In functional languages or immutable-data contexts, pass new copies at each level instead -- this trades space for correctness simplicity. - Many "backtracking" interview problems have DP solutions that are asymptotically faster for counting/optimizing. Always ask: "Do I need all solutions, or just the count/optimum?" before choosing backtracking. - For constraint satisfaction problems (CSP) at scale, dedicated CSP solvers (OR-Tools, Z3) vastly outperform hand-written backtracking. ## Related Units - [Dynamic Programming Patterns](/software/patterns/dynamic-programming/2026) - [Graph Algorithm Patterns](/software/patterns/graph-algorithms/2026) - [Binary Search Variations](/software/patterns/binary-search-variations/2026)