Practice Session 11: Backtracking

Overview

Backtracking is systematic trial and error with intelligent retreat: build a solution incrementally, and the moment you detect that the current partial solution cannot lead to a valid complete solution, abandon it and try the next alternative. This “prune early, recurse deep” structure makes backtracking the canonical algorithm for enumeration problems (find all valid configurations) and constraint-satisfaction problems (find any configuration satisfying hard rules). At senior level the key distinction is recognising when you can prune — sorted input enables early exit, conflict sets enable O(1) validity checks, and symmetry-breaking rules eliminate duplicate branches before they are explored.

Backtracking Template

Every backtracking problem shares the same recursive skeleton. Internalise this once; the rest is filling in goal_reached, valid(choice), and undo(choice).

backtrack(state, choices):
    if goal reached:
        record result
        return
    for each choice in choices:
        if valid(choice):           ← constraint check; prune here
            make choice             ← mutate state
            backtrack(state, remaining choices)
            undo choice             ← THE key step; restore state exactly

The undo choice step is what distinguishes backtracking from plain DFS. Without it, you are mutating shared state and cannot explore sibling branches correctly. In Java, “undo” means one of:

list.remove(list.size() - 1) for ArrayList-based state
board[r][c] = saved for in-place grid marking
used[i] = false for boolean arrays
set.remove(key) for conflict-tracking sets

Problem 1: Subsets

Link: LeetCode 78

Quick Summary: Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Industry Context: Power-set enumeration is the backbone of feature-flag combination testing — given n feature flags, QA automation must cover every meaningful combination. Backtracking over the power set (with pruning for mutually exclusive flags) is how test-case generators like combinatorial interaction testing (CIT) tools explore the configuration space without brute-forcing 2^n explicit test runs.

Approach 1: Iterative Bit Manipulation

// O(n × 2^n) time  O(n × 2^n) space
public static List<List<Integer>> subsetsBitMask(int[] nums) {
    int n = nums.length;
    List<List<Integer>> result = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> subset = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if ((mask & (1 << i)) != 0) subset.add(nums[i]);
        }
        result.add(subset);
    }
    return result;
}

Time: O(n × 2^n) — 2^n subsets, each costs O(n) to build
Space: O(n × 2^n) for the result
Tradeoff: No recursion overhead. Direct and readable. Does not extend naturally to problems that add constraints (e.g., “only subsets summing to k”) because there is no natural pruning point in the bit iteration.

Approach 2: Recursive Backtracking

// O(n × 2^n) time  O(n) stack depth + O(n × 2^n) result
public static List<List<Integer>> subsetsBacktrack(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}
 
private static void backtrack(int[] nums, int start,
                               List<Integer> current,
                               List<List<Integer>> result) {
    result.add(new ArrayList<>(current));       // every state is a valid subset
    for (int i = start; i < nums.length; i++) {
        current.add(nums[i]);                   // choose
        backtrack(nums, i + 1, current, result);// explore
        current.remove(current.size() - 1);     // undo  ← backtracking
    }
}

Time: O(n × 2
Space: O(n) recursion depth; O(n × 2^n) for the result
Key Insight: Recording current at the top of backtrack (before the loop) — rather than only at the base case — is what generates all subsets including the empty set and all proper subsets. Each recursive call effectively asks “subsets that include only elements from index start onward”, enforcing lexicographic non-duplication without sorting.

Problem 2: Permutations

Link: LeetCode 46

Quick Summary: Given an array nums of distinct integers, return all possible permutations in any order.

Industry Context: Permutation enumeration with cost-based pruning is exactly what SQL query plan optimisers do when enumerating join orderings. For a query joining n tables, there are n! possible orderings. The optimiser uses a backtracking search with a cost model to prune orderings whose partial plan cost already exceeds the best complete plan found so far — the same used[] structure prevents re-using a table already placed in the join order.

Approach 1: Swap-Based Permutation

// O(n × n!) time  O(n) extra space + O(n × n!) result
public static List<List<Integer>> permutationsSwap(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    permuteSwap(nums, 0, result);
    return result;
}
 
private static void permuteSwap(int[] nums, int start, List<List<Integer>> result) {
    if (start == nums.length) {
        List<Integer> perm = new ArrayList<>();
        for (int x : nums) perm.add(x);
        result.add(perm);
        return;
    }
    for (int i = start; i < nums.length; i++) {
        swap(nums, start, i);                       // choose: fix nums[i] at position start
        permuteSwap(nums, start + 1, result);       // explore
        swap(nums, start, i);                       // undo swap
    }
}

Time: O(n × n!)
Space: O(n) — uses the input array in-place, no used[] needed
Tradeoff: Minimal extra memory. However, the output permutations are not in lexicographic order (swap-based scrambles the remaining elements), which matters if the caller requires sorted output. Also harder to extend to the “permutations with duplicates” variant.

Approach 2: Backtracking with `used[]` Array

// O(n × n!) time  O(n) space for used[] + recursion
public static List<List<Integer>> permutationsBacktrack(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackPerms(nums, new boolean[nums.length], new ArrayList<>(), result);
    return result;
}
 
private static void backtrackPerms(int[] nums, boolean[] used,
                                   List<Integer> current,
                                   List<List<Integer>> result) {
    if (current.size() == nums.length) {
        result.add(new ArrayList<>(current));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;               // pruning: skip already-used elements
        used[i] = true;
        current.add(nums[i]);                // choose
        backtrackPerms(nums, used, current, result); // explore
        current.remove(current.size() - 1); // undo
        used[i] = false;                    // undo
    }
}

Time: O(n × n!)
Space: O(n) for used[] + O(n) recursion depth
Key Insight: The used[] array is the “currently committed choices” set. At any point in the recursion, used[i] == true means “index i is already on the path from root to current node in the decision tree”. This two-sided undo — current.remove() AND used[i] = false — is the canonical form and extends directly to the duplicates variant: sort nums first, then add if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue to skip duplicate branches.

Problem 3: Combination Sum

Link: LeetCode 39

Quick Summary: Given an array of distinct positive integers candidates and a target, return all unique combinations of candidates that sum to target. Each candidate may be used an unlimited number of times.

Industry Context: Package dependency resolution with version constraints — e.g., Cargo (Rust), Bundler (Ruby), pip — is structurally identical. Each package version is a “candidate”; the “target” is the set of version constraints that must all be satisfied. The solver backtracks over version assignments, pruning any branch where a chosen version already violates a constraint (analogous to candidates[i] > remaining). The “unlimited reuse” corresponds to multiple packages depending on the same library at the same version.

Approach 1: Unsorted Backtracking (No Early Exit)

// O(n^(T/min)) time  O(T/min) stack depth
public static List<List<Integer>> combinationSumBrute(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackBrute(candidates, target, 0, new ArrayList<>(), result);
    return result;
}
 
private static void backtrackBrute(int[] candidates, int remaining,
                                   int start, List<Integer> current,
                                   List<List<Integer>> result) {
    if (remaining == 0) { result.add(new ArrayList<>(current)); return; }
    if (remaining < 0) return;
    for (int i = start; i < candidates.length; i++) {
        current.add(candidates[i]);
        backtrackBrute(candidates, remaining - candidates[i], i, current, result);
        current.remove(current.size() - 1);
    }
}

Time: O(n^(T/min)) — T = target, min = smallest candidate
Space: O(T/min) recursion depth
Tradeoff: Correct but explores dead-end branches (e.g., tries candidate = 6 even when remaining = 3). Every remaining < 0 check occurs after an unnecessary recursive call, wasting stack frames.

Approach 2: Backtracking with Sort + Early-Exit Pruning

// O(n^(T/min)) worst case, much better in practice  O(T/min) stack depth
public static List<List<Integer>> combinationSumOptimal(int[] candidates, int target) {
    Arrays.sort(candidates);                    // enables break-based pruning
    List<List<Integer>> result = new ArrayList<>();
    backtrack(candidates, target, 0, new ArrayList<>(), result);
    return result;
}
 
private static void backtrack(int[] candidates, int remaining,
                               int start, List<Integer> current,
                               List<List<Integer>> result) {
    if (remaining == 0) { result.add(new ArrayList<>(current)); return; }
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > remaining) break;   // PRUNING: sorted → all subsequent also too large
        current.add(candidates[i]);
        backtrack(candidates, remaining - candidates[i], i, current, result);
        current.remove(current.size() - 1);
    }
}

Time: O(n^(T/min)) worst case; dramatically better average case
Space: O(T/min) recursion depth
Key Insight: Sorting is the prerequisite for the break (not continue) optimisation. With an unsorted array you can only continue past a too-large element; with a sorted array, once candidates[i] > remaining you know the entire suffix of the array is also too large. break prunes the right subtree of the decision tree in O(1) instead of entering it. This is the most important pruning strategy in combination/subset-sum problems and is valid whenever the input is sorted and the accumulated sum is monotonically non-decreasing as you add elements.

Problem 4: N-Queens

Link: LeetCode 51

Quick Summary: Place n queens on an n × n chessboard such that no two queens attack each other. Return all distinct solutions as board configurations.

Industry Context: N-Queens is the canonical model for resource scheduling with mutual exclusion constraints — assigning n jobs to n machines where certain (job, machine) pairs conflict (a job’s resource requirements clash with another job already scheduled on that machine). The three-set conflict detection (cols, diag1, diag2) maps directly to three types of resource contention: exclusive CPU slots, shared memory banks, and I/O channel conflicts. Real constraint solvers for distributed job schedulers (Kubernetes, YARN) use exactly this three-dimensional conflict tracking with O(1) lookup.

Approach 1: Brute Backtracking with O(n) Conflict Scan

// O(n!) time  O(n) space
public static List<List<String>> solveNQueensBrute(int n) {
    List<List<String>> result = new ArrayList<>();
    int[] queens = new int[n];   // queens[row] = column of queen in that row
    Arrays.fill(queens, -1);
    backtrackBrute(queens, 0, n, result);
    return result;
}
 
private static void backtrackBrute(int[] queens, int row, int n,
                                   List<List<String>> result) {
    if (row == n) { result.add(buildBoard(queens, n)); return; }
    for (int col = 0; col < n; col++) {
        if (isValid(queens, row, col)) {
            queens[row] = col;
            backtrackBrute(queens, row + 1, n, result);
            queens[row] = -1;
        }
    }
}
 
private static boolean isValid(int[] queens, int row, int col) {
    for (int r = 0; r < row; r++) {
        if (queens[r] == col) return false;
        if (Math.abs(queens[r] - col) == Math.abs(r - row)) return false;
    }
    return true;
}

Time: O(n!) — the recursion tree has n! leaves
Space: O(n) for queens array + recursion depth
Tradeoff: isValid scans all previously placed queens — O(n) per placement. For n = 12 this is fast enough; for large n (constraint solver scaling) the O(1) set-based approach is significantly faster.

Approach 2: Backtracking with Column/Diagonal Conflict Sets

// O(n!) time  O(n) space for sets + recursion
public static List<List<String>> solveNQueensOptimal(int n) {
    List<List<String>> result = new ArrayList<>();
    backtrack(new int[n], new HashSet<>(), new HashSet<>(), new HashSet<>(), 0, n, result);
    return result;
}
 
private static void backtrack(int[] queens,
                               Set<Integer> cols,
                               Set<Integer> diag1,   // row - col (same \ diagonal)
                               Set<Integer> diag2,   // row + col (same / diagonal)
                               int row, int n,
                               List<List<String>> result) {
    if (row == n) { result.add(buildBoard(queens, n)); return; }
    for (int col = 0; col < n; col++) {
        if (cols.contains(col)
                || diag1.contains(row - col)
                || diag2.contains(row + col)) continue;  // O(1) conflict check
        queens[row] = col;
        cols.add(col); diag1.add(row - col); diag2.add(row + col);  // choose
        backtrack(queens, cols, diag1, diag2, row + 1, n, result);  // explore
        cols.remove(col); diag1.remove(row - col); diag2.remove(row + col); // undo
        queens[row] = -1;
    }
}

Time: O(n!)
Space: O(n) for the three sets + O(n) recursion
Key Insight: The diagonal invariants row - col (constant on \ diagonals) and row + col (constant on / diagonals) are geometric identities from the chessboard. Storing these values in sets reduces conflict checking from O(n) scan to O(1) hash lookup. The three-set undo pattern (cols.remove, diag1.remove, diag2.remove) after the recursive call is the backtracking step — without it, constraints from one branch contaminate sibling branches.

Problem 5: Word Search

Link: LeetCode 79

Quick Summary: Given an m × n character grid and a string word, return true if word exists in the grid by traversing adjacent (4-directional) cells. Each cell may be used at most once.

Industry Context: Grid DFS backtracking with in-place marking is used in OCR post-processing — after a neural network emits a character grid, a backtracking word validator confirms that recognised characters form coherent paths through a character-confidence grid. The same pattern appears in network topology probes (can a packet reach a destination through an adjacency grid of nodes with current availability masks?) and in board-game AI for games like Boggle and Scrabble, where valid word paths must be discovered under letter-reuse constraints.

Approach 1: DFS with Explicit Visited Array

// O(m × n × 4^L) time  O(m × n) space for visited
public static boolean wordSearchBrute(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    boolean[][] visited = new boolean[rows][cols];
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (dfs(board, visited, word, r, c, 0)) return true;
    return false;
}
 
private static boolean dfs(char[][] board, boolean[][] visited,
                            String word, int r, int c, int idx) {
    if (idx == word.length()) return true;
    int rows = board.length, cols = board[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (visited[r][c] || board[r][c] != word.charAt(idx)) return false;
    visited[r][c] = true;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int[] d : dirs)
        if (dfs(board, visited, word, r + d[0], c + d[1], idx + 1)) {
            visited[r][c] = false;
            return true;
        }
    visited[r][c] = false;    // undo  ← backtracking
    return false;
}

Time: O(m × n × 4^L) — for each cell (m×n), DFS up to 4 branches for L characters
Space: O(m × n) for visited array + O(L) recursion stack
Tradeoff: Clear separation of concerns — board is never mutated. Requires allocating an extra m×n boolean array. For memory-constrained environments (embedded, GPU-side kernels), this overhead is unacceptable.

Approach 2: DFS Backtracking with In-Place Sentinel Marking

// O(m × n × 4^L) time  O(L) space — no visited array
public static boolean wordSearchOptimal(char[][] board, String word) {
    int rows = board.length, cols = board[0].length;
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++)
            if (dfs(board, word, r, c, 0)) return true;
    return false;
}
 
private static boolean dfs(char[][] board, String word, int r, int c, int idx) {
    if (idx == word.length()) return true;
    int rows = board.length, cols = board[0].length;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] != word.charAt(idx)) return false;
 
    char saved = board[r][c];
    board[r][c] = '#';             // choose: mark in-place (no extra array)
    boolean found = dfs(board, word, r + 1, c, idx + 1)
                 || dfs(board, word, r - 1, c, idx + 1)
                 || dfs(board, word, r, c + 1, idx + 1)
                 || dfs(board, word, r, c - 1, idx + 1);
    board[r][c] = saved;           // undo  ← restore board (backtracking step)
    return found;
}

Time: O(m × n × 4
Space: O(L) recursion stack only — no additional O(m×n) allocation
Key Insight: Overwriting board[r][c] with '#' is a valid visited marker because '#' cannot match any character in the word (assuming ASCII letters only). The restore board[r][c] = saved is exactly the backtracking undo step — after the recursive call returns, the board is in precisely the state it was before the choice was made, so sibling branches in the DFS see an unmodified board. The short-circuit || evaluation also provides implicit pruning: once one branch returns true, the remaining branches are not evaluated.

Pruning Strategies

Pruning is what separates an exponential search from a practical algorithm. Recognise these patterns:

1. Sorted Input → Early Break

When: The accumulated value (sum, length, etc.) is monotonically non-decreasing as you pick larger elements.
How: Sort candidates ascending; if candidates[i] already exceeds the remaining budget, break (not continue) — all subsequent elements are also too large.
Example: Combination Sum, Subsets with target sum.

2. Conflict Sets → O(1) Validity Check

When: The validity of a choice depends on previously-made choices that can be expressed as membership in a set.
How: Maintain sets of “committed” constraint values (column, diagonal keys); check membership in O(1) instead of scanning all previous decisions in O(depth).
Example: N-Queens (cols + two diagonal sets), Sudoku (row/col/box sets), register allocation.

3. Impossibility Conditions → Dead-End Pruning

When: You can prove a partial solution cannot be completed — e.g., remaining budget is exhausted, required characters are missing.
How: Check the “remaining slack” before recursing. If remaining < minPossibleAddition, prune immediately.
Example: Combination Sum (remaining < 0), Word Search (character mismatch before recursing), N-Queens (all columns in current row are conflicted).

4. Symmetry Breaking

When: Multiple branches are structurally identical due to symmetry in the input or problem.
How: After sorting, skip duplicate values at the same decision level: if (i > start && candidates[i] == candidates[i-1]) continue.
Example: Subsets II (LC 90), Permutations II (LC 47), Combination Sum II (LC 40). Not needed for LC 78/46/39 which guarantee distinct elements.

Key Takeaways

The Three Backtracking Archetypes

Archetype	Template Variation	Examples	Decision Per Level
Subsets	Record at every state, iterate from `start`	LC 78, 90, 77	Include or skip element at index `i`
Permutations	Record at leaf only, iterate from 0 using `used[]`	LC 46, 47	Which unused element to place next
Constraint Satisfaction	Record at leaf, prune on constraint violation	LC 51, 37 (Sudoku), 79	Which value to assign to current slot

Combination Sum sits between Subsets and CSP: it records at a specific goal state (sum = target), iterates from start like subsets, but the constraint is arithmetic.

Time Complexity Estimation

The rough formula: O(branching_factor^depth × work_per_node)

Problem	Branching Factor	Depth	Total
Subsets	2 (include/exclude)	n	O(2^n) nodes × O(n) copy = O(n × 2^n)
Permutations	n, n-1, n-2, …	n	O(n!) nodes × O(n) copy = O(n × n!)
Combination Sum	n (with reuse)	T/min	O(n^(T/min))
N-Queens	n columns	n rows	O(n!) with pruning
Word Search	4 directions	L (word length)	O(m × n × 4^L)

Pruning changes the constant and often removes entire subtrees, but does not change the asymptotic class in the worst case. State the worst case and mention that pruning makes it much faster in practice.

Space Complexity

Recursion stack depth = the depth of the decision tree = the main space cost
State size per frame = O(1) if using indices/flags; O(n) if copying a list per frame
Total space (excluding result): O(depth × state_size_per_frame)
For most backtracking problems: O(n) or O(L) where L is the word/path length

When NOT to Use Backtracking

Situation	Better Approach	Why
”Count” or “minimum/maximum” over all valid configs	Dynamic Programming	DP memoises overlapping subproblems; backtracking recomputes them. If `backtrack(state)` is called with the same `state` from different paths, use DP.
”Find the shortest path”	BFS	BFS guarantees minimum depth; backtracking may find a long path first.
”Is there any valid assignment?” (not all) + overlapping subproblems	DP / Greedy	Coin Change (LC 322) looks like Combination Sum but “minimum count” requires DP, not backtracking enumeration.
Unique values already exist, choices are independent	Greedy	If each choice is locally optimal and does not constrain future choices, greedy is O(n log n) vs. backtracking’s exponential.

The key test: draw the recursion tree and ask “are there repeated subproblems (same state reached multiple ways)?” If yes → DP. If the subproblems are always distinct and you need all solutions → backtracking.

Pattern Recognition Triggers

“Find all combinations / subsets / permutations / arrangements” → Backtracking (enumerate)
“Is there any valid placement / assignment?” with hard constraints → Backtracking (CSP)
“Generate all strings / paths matching a pattern” → Backtracking with string state
Backtracking on a grid: “path exists” + “each cell used at most once” → DFS + in-place sentinel or visited[]
If you see target - current_sum decreasing through recursion → Combination Sum archetype; sort + break

Common Pitfalls

Forgetting the undo step: mutating state (list, array, board) without restoring it means sibling branches in the recursion tree see corrupted state. Every make choice must have a corresponding undo choice after the recursive call.
Shallow copy vs. deep copy of results: result.add(current) adds a reference; after backtracking, current will change. Always do result.add(new ArrayList<>(current)).
continue vs. break in pruning: use continue to skip one candidate; use break only when the remaining candidates are guaranteed to be worse (requires sorted input and monotone constraints).
Confusing backtracking with DP: if the problem asks for a count or minimum, think DP before backtracking. Coin Change, Word Break, and House Robber all look backtrackable but have overlapping subproblems that DP handles in polynomial time.
Infinite recursion from unrestricted reuse: in Combination Sum the next recursive call passes i (not i+1) to allow reuse of the same element. Forgetting this generates only non-reusing combinations; passing i-1 causes infinite recursion.

System Design Connections

Backtracking Pattern	System Design Analogue
Permutations with pruning	SQL optimiser join-order enumeration (System R dynamic programming over subsets is backtracking + memoisation)
N-Queens / CSP	Kubernetes scheduler: assign pods to nodes satisfying anti-affinity, resource, and taint constraints — backtrack on first constraint violation
Combination Sum	Cargo/pip/Bundler dependency solver: assign a version to each package satisfying all `>= / <= / ==` constraints; prune version assignments that immediately violate a known constraint
Word Search	Regular expression NFA matching with backtracking (grep, Java `Pattern`): advance through the regex, backtrack on mismatch, explore alternation branches
Subsets	Feature-flag combination testing matrix; CI/CD pipeline configuration space exploration

Study Notes by Niladri & AI

Explorer

Session-11-Backtracking

Practice Session 11: Backtracking

Overview

Backtracking Template

Problem 1: Subsets

Approach 1: Iterative Bit Manipulation

Approach 2: Recursive Backtracking

Problem 2: Permutations

Approach 1: Swap-Based Permutation

Approach 2: Backtracking with `used[]` Array

Problem 3: Combination Sum

Approach 1: Unsorted Backtracking (No Early Exit)

Approach 2: Backtracking with Sort + Early-Exit Pruning

Problem 4: N-Queens

Approach 1: Brute Backtracking with O(n) Conflict Scan

Approach 2: Backtracking with Column/Diagonal Conflict Sets

Problem 5: Word Search

Approach 1: DFS with Explicit Visited Array

Approach 2: DFS Backtracking with In-Place Sentinel Marking

Pruning Strategies

1. Sorted Input → Early Break

2. Conflict Sets → O(1) Validity Check

3. Impossibility Conditions → Dead-End Pruning

4. Symmetry Breaking

Key Takeaways

The Three Backtracking Archetypes

Time Complexity Estimation

Space Complexity

When NOT to Use Backtracking

Pattern Recognition Triggers

Common Pitfalls

System Design Connections

Graph View

Table of Contents

Backlinks

Study Notes by Niladri & AI

Explorer

Session-11-Backtracking

Practice Session 11: Backtracking

Overview

Backtracking Template

Problem 1: Subsets

Approach 1: Iterative Bit Manipulation

Approach 2: Recursive Backtracking

Problem 2: Permutations

Approach 1: Swap-Based Permutation

Approach 2: Backtracking with used[] Array

Problem 3: Combination Sum

Approach 1: Unsorted Backtracking (No Early Exit)

Approach 2: Backtracking with Sort + Early-Exit Pruning

Problem 4: N-Queens

Approach 1: Brute Backtracking with O(n) Conflict Scan

Approach 2: Backtracking with Column/Diagonal Conflict Sets

Problem 5: Word Search

Approach 1: DFS with Explicit Visited Array

Approach 2: DFS Backtracking with In-Place Sentinel Marking

Pruning Strategies

1. Sorted Input → Early Break

2. Conflict Sets → O(1) Validity Check

3. Impossibility Conditions → Dead-End Pruning

4. Symmetry Breaking

Key Takeaways

The Three Backtracking Archetypes

Time Complexity Estimation

Space Complexity

When NOT to Use Backtracking

Pattern Recognition Triggers

Common Pitfalls

System Design Connections

Graph View

Table of Contents

Backlinks

Approach 2: Backtracking with `used[]` Array