DSA Search patterns

Backtracking

N-queens at n = 12 expands a that only correct pruning keeps finite enough to finish. Recursion is control flow; state, constraints, and are the algorithm.

Build a partial answer, branches that cannot work, restore state, try the next choice.

Algorithm journey

Choose

Extend the path; update constraint structures.

Prove the prefix still deserves exploration.

Explore

Recurse; collect solutions at complete leaves.

Restore state for the next sibling.

What actually happens

Naive idea: generate every full assignment, then test. Correct, and hopeless when the product of domain sizes explodes before any check runs.

Better idea: test as you go. If a prefix already attacks a queen or exceeds capacity, the entire subtree. Always so siblings see a clean state.

The improved design still fails when pruning is unjustified (deletes valid answers), when undo is incomplete, when the live path is saved without copying, or when blow-up is ignored.

Invariant

On entry to search(state), the state represents exactly the choices on the current root-to-node path and satisfies every hard constraint checked so far. On return, state is restored to its entry value. A prune is allowed only if no valid completion of that prefix exists (or none can improve the bound).

How to choose backtracking

1. Need all solutions or constructive search? Backtracking fits. Pure counting/optimization may admit DP.

2. Strong early constraints? Pruning pays; without them, you are brute force with recursion cosmetics.

3. Can you undo cheaply? Incremental masks beat rebuilding boards each time.

Quantitative check

N-queens without pruning explores on the order of nⁿ placements conceptually; with attack pruning, n = 8 is instant and n = 14 is still searchable. Permutations of length 12 are 12! ≈ 4.8×10⁸: listing them all is already an output problem.

The mental model: make, search, restore

Choose

Add a candidate to the path and update every constraint structure so the state remains valid.

Explore

Recurse on the smaller decision. Stop immediately if a feasibility or bound check proves a dead end.

Unchoose

Reverse every mutation. A sibling must see exactly the state its parent had before this choice.

Core invariant: on entry to search(state), the state represents exactly the choices on the current root-to-node path. On return, it is byte-for-byte or logically equivalent to its state on entry. This makes every recursive call independently understandable.

See the choice tree evolve

The tree is conceptual. It is normally generated on demand, not stored. In the trace below, equal values A₁ and A₂ have different indices. Compare naive index choices with the same-depth rule that keeps only unique value sequences.

Choice-tree explorer: permutations of A, A, B

Step through the DFS. Toggle pruning to compare distinct indices with distinct values.

1. Choose

mutate state

2. Explore

recurse or prune

3. Unchoose

restore state

Live path

∅

Recursive calls

Recorded leaves

Unique outputs

current path solution pruned explored

startStep 1 / 23

Begin with an empty path and three available items.

Each A has a different index, even though both carry the same value.

Pruning uses a set local to one recursion depth. A global “seen A” set would incorrectly erase valid A choices deeper in the path.

What lives in a backtracking state?

Path

Choices made so far: selected numbers, placed queens, filled cells, or a partial word.

Frontier

What may be chosen next: an index, remaining items, neighbors, or legal values for a variable.

Constraints

Fast validity data such as used sets, row/diagonal masks, remaining capacity, or a running sum.

Result policy

Return on the first witness, count leaves, copy every answer, or update the best answer seen.

Tree part	Meaning	Question to ask
Node	One partial assignment	What facts are true after this path?
Edge	One reversible choice	How do I apply and exactly undo it?
Leaf	A solution or dead end	Is it complete, invalid, or impossible to improve?
Subtree	All completions of a prefix	Can one proof safely discard all of them?

One search engine, different goals

Decision

“Does any solution exist?” Return True after the first witness. Choice ordering can greatly change runtime even when worst-case complexity is unchanged.

Enumeration / counting

Visit every valid leaf to list or count answers. You cannot asymptotically beat the size of an explicitly requested output.

Optimization

Track the best complete answer and prune when an optimistic bound cannot beat it. This is backtracking plus branch and bound.

Reusable templates

Put the base case and pruning checks before generating children. Keep every mutation next to its inverse; that visual pairing prevents most restoration bugs.

Enumerate with one mutable path

Python

python

def backtrack(state, path, answers):
    if violates_constraint(state):
        return                    # prune the whole subtree

    if is_complete(state):
        answers.append(path.copy())
        return

    for choice in candidates(state):
        if not is_legal(state, choice):
            continue

        apply(state, path, choice)     # choose
        backtrack(state, path, answers) # explore
        undo(state, path, choice)      # unchoose

Java

java

import java.util.ArrayList;
import java.util.List;

abstract class EnumeratingBacktracker<S, C> {
    void backtrack(S state, List<C> path, List<List<C>> answers) {
        if (violatesConstraint(state)) return; // prune the whole subtree

        if (isComplete(state)) {
            answers.add(new ArrayList<>(path));
            return;
        }

        for (C choice : candidates(state)) {
            if (!isLegal(state, choice)) continue;

            apply(state, path, choice);              // choose
            backtrack(state, path, answers);         // explore
            undo(state, path, choice);               // unchoose
        }
    }

    abstract boolean violatesConstraint(S state);
    abstract boolean isComplete(S state);
    abstract Iterable<C> candidates(S state);
    abstract boolean isLegal(S state, C choice);
    abstract void apply(S state, List<C> path, C choice);
    abstract void undo(S state, List<C> path, C choice);
}

Stop at the first witness

Python

python

def exists(state, path):
    if is_goal(state):
        return True

    for choice in ordered_candidates(state):
        if not is_legal(state, choice):
            continue

        apply(state, path, choice)
        found = exists(state, path)
        undo(state, path, choice)  # restore before any return

        if found:
            return True
    return False

Java

java

import java.util.List;

abstract class WitnessBacktracker<S, C> {
    boolean exists(S state, List<C> path) {
        if (isGoal(state)) return true;

        for (C choice : orderedCandidates(state)) {
            if (!isLegal(state, choice)) continue;

            apply(state, path, choice);
            boolean found = exists(state, path);
            undo(state, path, choice); // restore before any return

            if (found) return true;
        }
        return false;
    }

    abstract boolean isGoal(S state);
    abstract Iterable<C> orderedCandidates(S state);
    abstract boolean isLegal(S state, C choice);
    abstract void apply(S state, List<C> path, C choice);
    abstract void undo(S state, List<C> path, C choice);
}

Mutable or immutable? Copying a tiny state into each recursive call is often clearer and perfectly acceptable. Mutate + undo is valuable when copies are expensive or tight performance matters. If you mutate, restoration must run on every path, including early success and exceptions.

Pruning: prove before you cut

A prune is correct only when no descendant of the current prefix can be needed. Good pruning usually changes practical runtime more than micro-optimizing the recursion.

Feasibility pruning

The prefix already violates a hard rule: two queens attack, a word is not a trie prefix, or a capacity became negative. No extension can repair it.

Monotone pruning

With sorted positive candidates, once candidate > remaining, every later candidate is too large too. Sorting turns one failure into a safe break.

Bound pruning

Even an optimistic completion cannot beat the incumbent best answer. Common in scheduling, knapsack variants, and traveling-salesperson search.

Constraint propagation

A choice reduces domains of future variables. Pick the most constrained variable first and fail early: the “minimum remaining values” heuristic used in Sudoku-like CSPs.

Duplicate choices and symmetry

Duplicates are equal input values; symmetries are different-looking choices that encode equivalent solutions. In both cases, choose one canonical representative. Sort first, then skip an equal candidate only when its earlier equal sibling was not used on the current path.

Python

python

def unique_permutations(nums):
    nums.sort()
    used = [False] * len(nums)
    path, out = [], []

    def dfs():
        if len(path) == len(nums):
            out.append(path.copy())
            return

        for i, value in enumerate(nums):
            if used[i]:
                continue
            # Same value + same depth => equivalent sibling subtree.
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue

            used[i] = True
            path.append(value)
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return out

Java

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

final class UniquePermutations {
    static List<List<Integer>> generate(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        dfs(nums, new boolean[nums.length], new ArrayList<>(), out);
        return out;
    }

    private static void dfs(
            int[] nums, boolean[] used, List<Integer> path,
            List<List<Integer>> out) {
        if (path.size() == nums.length) {
            out.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            // Same value + same depth => equivalent sibling subtree.
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;

            used[i] = true;
            path.add(nums[i]);
            dfs(nums, used, path, out);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

Why not used[i - 1]? It means the earlier equal value is not an ancestor in this path, so it must be an already represented sibling. Equal values are still allowed at different depths. For combinations driven by a start index, the equivalent rule isif i > start and nums[i] == nums[i - 1]: continue.

Representative shapes

Problem family	Choice at one level	State / uniqueness	Search shape
Subsets	Include or exclude item `i`	`(i, path)`; fixed input order	`2ⁿ` leaves
Combinations	Pick next index from `start…n-1`	Increasing indices break order symmetry	Only requested sizes / sums
Permutations	Pick any unused item	Path + used set or in-place swap	`n!` leaves if distinct
N-Queens / Sudoku	Assign one legal position/value	Incremental row, column, box, diagonal constraints	Irregular, heavily pruned
Word search	Move to an unvisited neighbor	Cell + visited marks + prefix	Up to four branches per character

Example: combinations that reach a target

Sorting supports both duplicate elimination and a monotone early break. Advancing toi + 1 means each input occurrence is used at most once.

Python

python

def combination_sum_once(nums, target):
    nums.sort()
    out, path = [], []

    def dfs(start, remaining):
        if remaining == 0:
            out.append(path.copy())
            return

        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i - 1]:
                continue             # equal sibling
            if nums[i] > remaining:
                break                # later values are larger

            path.append(nums[i])
            dfs(i + 1, remaining - nums[i])
            path.pop()

    dfs(0, target)
    return out

Java

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

final class CombinationSumOnce {
    static List<List<Integer>> solve(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> out = new ArrayList<>();
        dfs(nums, 0, target, new ArrayList<>(), out);
        return out;
    }

    private static void dfs(
            int[] nums, int start, int remaining,
            List<Integer> path, List<List<Integer>> out) {
        if (remaining == 0) {
            out.add(new ArrayList<>(path));
            return;
        }

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

            path.add(nums[i]);
            dfs(nums, i + 1, remaining - nums[i], path, out);
            path.remove(path.size() - 1);
        }
    }
}

Example: N-Queens with O(1) checks

Placing exactly one queen per row removes row conflicts by construction. Sets make the remaining column and diagonal checks constant time.

Python

python

def solve_n_queens(n):
    cols, down, up = set(), set(), set()
    board = [-1] * n
    out = []

    def dfs(row):
        if row == n:
            out.append(board.copy())
            return

        for col in range(n):
            d1, d2 = row - col, row + col
            if col in cols or d1 in down or d2 in up:
                continue

            board[row] = col
            cols.add(col); down.add(d1); up.add(d2)
            dfs(row + 1)
            cols.remove(col); down.remove(d1); up.remove(d2)
            board[row] = -1

    dfs(0)
    return out

Java

java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

final class NQueens {
    static List<int[]> solve(int n) {
        int[] board = new int[n];
        Arrays.fill(board, -1);
        List<int[]> out = new ArrayList<>();
        dfs(0, board, new HashSet<>(), new HashSet<>(), new HashSet<>(), out);
        return out;
    }

    private static void dfs(
            int row, int[] board, Set<Integer> cols,
            Set<Integer> down, Set<Integer> up, List<int[]> out) {
        if (row == board.length) {
            out.add(Arrays.copyOf(board, board.length));
            return;
        }

        for (int col = 0; col < board.length; col++) {
            int d1 = row - col;
            int d2 = row + col;
            if (cols.contains(col) || down.contains(d1) || up.contains(d2)) continue;

            board[row] = col;
            cols.add(col); down.add(d1); up.add(d2);
            dfs(row + 1, board, cols, down, up, out);
            cols.remove(col); down.remove(d1); up.remove(d2);
            board[row] = -1;
        }
    }
}

Complexity is about visited nodes, and output

The useful accounting rule istime = visited search nodes × work per node + output-copy cost. A rough O(bᵈ) bound uses maximum branching factor b and depth d, but shrinking candidate sets often give tighter factorial or binomial bounds.

Enumeration	Leaves	Time when copying answers	Auxiliary space
All subsets	`2ⁿ`	`Θ(n · 2ⁿ)`	`O(n)`
All permutations	`n!`	`Θ(n · n!)`	`O(n)`
All size-`k` combinations	`C(n, k)`	`Ω(k · C(n, k))`	`O(k)`
N-Queens	solution-dependent	`O(n!)` common upper bound	`O(n)` plus output

Output-sensitive lower bound

If the problem asks for all S answers of length L, merely materializing them costs Ω(S · L). Exponential runtime is therefore sometimes required by the request, not evidence of a poor algorithm.

Space accounting

Excluding returned answers, a shared path and recursion stack usually use O(d) space, plus constraint structures. Copying state at every depth can raise peak space towardO(d²) when each copy has size O(d).

Backtracking, DP, and plain DFS

Backtracking

Search different assignments, maintain constraints, and undo. Best when paths themselves matter or strong pruning separates prefixes.

Memoization / DP

Cache when many paths reach the same future-relevant state such as (index, mask, remaining). DP often fits counting or optimization better than listing every path.

Graph DFS

Traverses an explicit graph, often with a global visited set. Backtracking usually marks a choice only for the current path and unmarks it so another path may reuse it.

Memoization warning: cache only a state description that contains everything affecting future answers. Two equal-looking positions may not be equivalent if their used sets, constraints, or required output prefixes differ.

A practical design checklist

1
Define one level
What single decision does depth d represent? Fixed levels prevent duplicate orderings.
2
Name the state
Write the exact path, frontier, constraints, and result policy before coding.
3
State the invariant
What is guaranteed on function entry, and what must be restored on exit?
4
Write the base case
Distinguish a complete solution from a dead end; record copies, not mutable aliases.
5
Generate canonical choices
Use start indices, sorting, or symmetry rules so equivalent branches have one owner.
6
Add cheap pruning first
Check legality incrementally; expensive bounds should save more work than they cost.
7
Pair choose with undo
Update every field in one block and reverse those fields in the opposite order.
8
Trace the smallest duplicate input
Inputs like [1, 1, 2] expose scope errors in visited and duplicate checks.

Common failure modes

Returning before undo: a successful child leaves shared state dirty for its callers.
Saving the live path: append path.copy(), or every answer may reference the same final list.
Using global visited for a path rule: it can forbid valid reuse in sibling branches.
Skipping every equal value: duplicate checks belong to one depth; equal ancestors can still be required.
Pruning without a proof: a condition that “usually cannot work” silently deletes valid solutions.
Rechecking constraints from scratch: incremental sets, counters, or bitmasks turn repeated scans into O(1) checks.
Ignoring output cost: an algorithm cannot list exponentially many answers in polynomial time.

Exercises

Give a pruning rule for N-queens that is incorrect (deletes a valid board). What failed in the prune correctness claim?
On input [1,1,2], trace where a global visited set produces wrong unique permutations versus a same-depth skip rule.
You must list all subsets of size k from n = 40. Why is “O(2ⁿ)” the wrong complexity story once you stream the output?

Primary sources

Knuth, D.: Dancing Links / exact cover (systematic backtracking with dancing data structures).
Cormen et al., CLRS: backtracking as exhaustive search with pruning (related discussion in NP / search chapters).
Russell & Norvig, AIMA: constraint satisfaction, forward checking, and backtracking search.

Takeaway

Backtracking is reversible DFS with a prune correctness proof. Choose, check, recurse, undo. The fastest branch is the one a true invariant lets you skip.

Backtracking

What actually happens

How to choose backtracking

Quantitative check

The mental model: make, search, restore

Choose

Explore

Unchoose

See the choice tree evolve

Choice-tree explorer: permutations of A, A, B

What lives in a backtracking state?

Path

Frontier

Constraints

Result policy

One search engine, different goals

Decision

Enumeration / counting

Optimization

Reusable templates

Enumerate with one mutable path

Python

Java

Stop at the first witness

Python

Java

Pruning: prove before you cut

Feasibility pruning

Monotone pruning

Bound pruning

Constraint propagation

Duplicate choices and symmetry

Python

Java

Representative shapes

Example: combinations that reach a target

Python

Java

Example: N-Queens with O(1) checks

Python

Java

Complexity is about visited nodes, and output

Output-sensitive lower bound

Space accounting

Backtracking, DP, and plain DFS

Backtracking

Memoization / DP

Graph DFS

A practical design checklist

Define one level

Name the state

State the invariant

Write the base case

Generate canonical choices

Add cheap pruning first

Pair choose with undo

Trace the smallest duplicate input

Common failure modes

Exercises

Primary sources

Takeaway