Backtracking: Subsets, Permutations & Combinations

Dynamic programming, which closed the previous module, works when a problem has overlapping subproblems we can tabulate. But a great many problems ask us instead to enumerate or search a combinatorial space: list every subset, every permutation, every way to place eight queens, every assignment satisfying a formula. These spaces are exponential, so we cannot afford to materialize them, yet we can traverse them selectively. Backtracking is the disciplined depth-first walk of such a space: it builds a candidate solution one decision at a time and abandons a partial candidate the instant it proves it cannot be extended to a valid complete one.¹ This act of abandonment, the backtrack, is what separates a directed search from blind brute force.

This lesson opens the module by establishing the paradigm and instantiating it on the three enumerations every later technique builds on (subsets, permutations, and combinations) together with the two ideas that make backtracking fast in practice: deduplication of equal choices and pruning of infeasible subtrees.

The paradigm: choose, explore, un-choose

Think of a solution as a sequence of decisions. At each step we have a partial solution and a set of valid choices to extend it. We pick one choice, recurse to extend further, and then undo that choice before trying the next one. The recursion thus traverses a state-space tree (also called a decision tree or choice tree): the root is the empty partial solution, each edge is one choice, each node is the partial solution accumulated so far, and the leaves are complete candidates.² The walk is depth-first.

The un-choose step is what lets a single mutable buffer serve the entire tree: by the time control returns from a child, the buffer is byte-for-byte what it was before we descended, so the next sibling starts from a clean slate.

One mutable buffer across a node: \textbf{choose} pushes

c

, \textbf{explore} recurses, \textbf{un-choose} pops — restoring the buffer exactly so the next sibling starts clean

Algorithm:

\textsc{Backtrack}(partial)

— generic DFS over the state-space tree

1
if $\textsc{IsComplete}(partial)$ then
2
record a copy of $partial$
3
return
4
for each $c \in \textsc{ValidChoices}(partial)$ do
5
if $\textsc{Prune}(partial, c)$ then
6
continue
prune
7
$\textsc{Apply}(partial, c)$
choose
8
$\textsc{Backtrack}(partial)$
explore
9
$\textsc{Undo}(partial, c)$
un-choose

Everything in this lesson is a specialization of this skeleton: the four primitives $IsComplete$ , $ValidChoices$ , $Prune$ , and the choose/undo pair are all we ever change.

Subsets: the power set in $2^{n}$

The cleanest decision tree is the power set of ${a_{0}, \dots, a_{n - 1}}$ . Each element faces one binary decision, in the subset or out, so the tree is a perfect binary tree of depth $n$ , and its $2^{n}$ leaves enumerate the $2^{n}$ subsets. This is the include–exclude recursion:

Algorithm:

\textsc{Subsets}(a, i, partial)

— include/exclude each element

1
if $i = n$ then
2
record a copy of $partial$
3
return
4
$\textsc{Subsets}(a, i+1, partial)$
exclude $a_i$
5
$partial.\text{push}(a_i)$
include $a_i$
6
$\textsc{Subsets}(a, i+1, partial)$
explore
7
$partial.\text{pop}()$
un-choose

DFS over the include/exclude choice tree for subsets of

{1, 2, 3}

. Each level decides one element in or out; edge

- i

excludes

a_{i}

+ i

includes it.

An equivalent and often handier formulation uses a start index so that every node, not only the leaves, is a valid subset. We loop over choices $a_{i}, a_{i + 1}, \dots$ , and each recursion only ever looks forward from the chosen index, which guarantees we generate each subset once, in lexicographic order of indices:

Algorithm:

\textsc{Subsets}(a, start, partial)

— emit every node, advance start

1
record a copy of $partial$
every node is a subset
2
for $i \gets start$ to $n-1$ do
3
$partial.\text{push}(a_i)$
choose $a_i$
4
$\textsc{Subsets}(a, i+1, partial)$
forward only
5
$partial.\text{pop}()$
un-choose

Advancing the start index to $i + 1$ in the recursive call is what stops the same subset ${1, 2}$ from being generated twice, once as $1$ -then- $2$ and once as $2$ -then- $1$ : an element earlier in the array is never chosen after a later one. Both formulations do $O (2^{n})$ recursive calls and spend $O (n)$ to copy each emitted subset, for $Θ (n \cdot 2^{n})$ total, unavoidable, since the output itself has that size.

subsets.pypython

from typing import Sequence, TypeVar
from comparable import Comparable


Element = TypeVar("Element", bound=Comparable)


def subsets_include_exclude(elements: Sequence[Element]) -> list[list[Element]]:
  """
    Every subset of `elements`, via the include/exclude binary recursion.\n
    Each element faces one decision — in the subset or out — so the choice\n
    tree is a perfect binary tree of depth n with 2^n leaves.\n
  """
  size: int = len(elements)
  results: list[list[Element]] = []
  partial: list[Element] = []

  def explore(index: int) -> None:
    if index == size:
      results.append(list(partial))
      return

    # exclude elements[index].
    explore(index + 1)

    # include elements[index], then un-choose to restore the buffer.
    partial.append(elements[index])
    explore(index + 1)
    partial.pop()

  explore(0)
  return results


def subsets(elements: Sequence[Element]) -> list[list[Element]]:
  """
    Every subset of `elements`, via the forward-only start-index recursion.\n
    Each node emits its own `partial`, and recursion only ever looks forward\n
    from the chosen index, so each subset is generated once in lexicographic\n
    order of indices.\n
  """
  size: int = len(elements)
  results: list[list[Element]] = []
  partial: list[Element] = []

  def explore(start: int) -> None:

    # every node is a subset.
    results.append(list(partial))

    # extend with each later element — forward only, never an earlier index.
    for index in range(start, size):
      partial.append(elements[index])
      explore(index + 1)
      partial.pop()

  explore(0)
  return results

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Permutations: $n!$ orderings

A permutation uses every element, so completeness is all $n$ chosen, and the valid choices at each step are the elements not yet used. We track membership with a boolean used[] array; the branching factor shrinks from $n$ at the root to $n - 1$ , then $n - 2$ , giving exactly $n \cdot (n - 1) \dots 1 = n!$ leaves.

Algorithm:

\textsc{Permute}(a, used, partial)

— pick an unused element each step

1
if $|partial| = n$ then
2
record a copy of $partial$
3
return
4
for $i \gets 0$ to $n-1$ do
5
if $used[i]$ then continue
not a valid choice
6
$used[i] \gets \text{true}$ ; $partial.\text{push}(a_i)$
choose
7
$\textsc{Permute}(a, used, partial)$
explore
8
$partial.\text{pop}()$ ; $used[i] \gets \text{false}$
un-choose

An alternative avoids the auxiliary array by swapping in place: to permute $a [k .. n - 1]$ , swap each candidate into position $k$ , recurse on $a [k + 1.. n - 1]$ , then swap it back: the swap-back is the un-choose. Either way the work is $Θ (n \cdot n!)$ , dominated by emitting $n!$ permutations of length $n$ .

Permutation state-space tree for

{1, 2, 3}

— the branching shrinks

3 \to 2 \to 1

as elements are consumed, giving

3! = 6

leaves

Each root-to-leaf path consumes every element exactly once; the accented path (root $\to 2 \to 3 \to 1$ ) builds the permutation $231$ . The fan-out is $3$ at the root, $2$ at depth one, and $1$ at depth two, so the leaf count is the falling product $3 \cdot 2 \cdot 1 = 3!$ .

permutations.pypython

from typing import Sequence, TypeVar

from comparable import Comparable

Element = TypeVar("Element", bound=Comparable)

def permutations(elements: Sequence[Element]) -> list[list[Element]]:
  """
    Every permutation of `elements`, picking an unused element each step.\n
    A boolean `used` array records which elements are already in `partial`;\n
    the branching factor shrinks n, n-1, ..., 1, giving exactly n! leaves.\n
  """
  size: int = len(elements)
  results: list[list[Element]] = []
  partial: list[Element] = []
  used: list[bool] = [False for _ in range(size)]

  def explore() -> None:
    if len(partial) == size:
      results.append(list(partial))
      return

    for index in range(size):

      # skip an element already placed on this path.
      if used[index]:
        continue

      # choose, recurse on the rest, then un-choose.
      used[index] = True
      partial.append(elements[index])
      explore()
      partial.pop()
      used[index] = False

  explore()
  return results

def permutations_in_place(elements: Sequence[Element]) -> list[list[Element]]:
  """
    Every permutation of `elements`, by swapping in place.\n
    To permute the suffix from `position`, swap each candidate into that\n
    slot, recurse on the rest, then swap it back to restore the array.\n
  """
  working: list[Element] = list(elements)
  size: int = len(working)
  results: list[list[Element]] = []

  def explore(position: int) -> None:
    if position == size:
      results.append(list(working))
      return
    for candidate in range(position, size):

      # swap the candidate into `position` (choose).
      working[position], working[candidate] = (
        working[candidate],
        working[position],
      )

      explore(position + 1)

      # swap it back (un-choose).
      working[position], working[candidate] = (
        working[candidate],
        working[position],
      )

  explore(0)
  return results

def permutations_with_duplicates(
  elements: Sequence[Element],
) -> list[list[Element]]:
  """
    Every distinct permutation of a multiset such as [1, 1, 2].\n
    Sort, then at each level skip an unused value equal to its predecessor\n
    whose predecessor is also unused at this depth, so each ordering of\n
    equal elements is emitted once.\n
  """
  ordered: list[Element] = sorted(elements)
  size: int = len(ordered)
  results: list[list[Element]] = []
  partial: list[Element] = []
  used: list[bool] = [False for _ in range(size)]

  def explore() -> None:
    if len(partial) == size:
      results.append(list(partial))
      return

    for index in range(size):

      # skip an element already placed on this path.
      if used[index]:
        continue

      # skip a duplicate whose equal predecessor is unused: the first of the
      # equal group already took that branch.
      if (
        index > 0
        and ordered[index] == ordered[index - 1]
        and not used[index - 1]
      ):
        continue

      # choose, recurse on the rest, then un-choose.
      used[index] = True
      partial.append(ordered[index])
      explore()
      partial.pop()
      used[index] = False

  explore()
  return results

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Combinations: $(k n)$ with a start index

A combination is a subset of a fixed size $k$ where order does not matter. We want ${1, 3}$ but not also ${3, 1}$ , so we reuse the start-index trick from subsets, which generates each combination exactly once by only ever choosing forward. Completeness is now we have collected $k$ elements.

Algorithm:

\textsc{Combine}(n, k, start, partial)

— choose

k

in increasing order

1
if $|partial| = k$ then
2
record a copy of $partial$
3
return
4
for $i \gets start$ to $n$ do
5
$partial.\text{push}(i)$
choose $i$
6
$\textsc{Combine}(n, k, i+1, partial)$
forward only
7
$partial.\text{pop}()$
un-choose

The start index does the combinatorial bookkeeping: because the chosen indices strictly increase along any root-to-leaf path, each $k$ -subset corresponds to exactly one path, and we enumerate all $(k n)$ of them with no duplicates. This is the same idea as the start-index subset enumerator: a combination is simply a subset enumeration cut off at depth $k$ .

combinations.pypython

def combinations(count: int, choose: int) -> list[list[int]]:
  """
    Every way to choose `choose` of the integers 1..count, in increasing\n
    order. Completeness is "we have collected `choose` elements."\n
  """
  results: list[list[int]] = []
  partial: list[int] = []

  def explore(start: int) -> None:
    if len(partial) == choose:
      results.append(list(partial))
      return

    # prune: stop once too few candidates remain to reach `choose`.
    remaining_needed: int = choose - len(partial)
    last_start: int = count - remaining_needed + 1

    # take each value, recurse forward to force increasing choices, undo.
    for value in range(start, last_start + 1):
      partial.append(value)
      explore(value + 1)
      partial.pop()

  explore(1)
  return results

Handling duplicates: skip equal siblings

When the input multiset contains repeated values, say $[1, 2, 2]$ , the naive enumerator emits the same combination twice, because the two $2$ s are distinguishable by position but identical in value. The standard fix is to sort the array, then at each level skip a choice equal to the one just tried at the same depth.

The condition $i > s t a r t$ carries the logic. The first occurrence of a value at a given level (when $i = s t a r t$ ) is always allowed; we only skip subsequent equal values at the same depth.

This is a soundness claim about the prune: a pruning rule is sound when it never discards a branch that contains a solution we have not already found elsewhere, so a sound prune keeps the search complete — every distinct solution is still reported.

The rule skips equal siblings, not equal ancestors: choosing $a_{i - 1}$ then descending and choosing $a_{i} = a_{i - 1}$ is legitimate (it uses both copies), and there $i = s t a r t$ so the guard does not fire.

Sorted

[1, 2, 2]

: the second equal sibling at a level (

i > s t a r t, a_{i} = a_{i - 1}

) is skipped, dropping a duplicate subtree (dashed, red); ancestor reuse

{2, 2}

survives

At the root, $a_{2} = 2$ repeats sibling $a_{1} = 2$ (here $i > s t a r t$ ), so its whole subtree is pruned as a duplicate. Inside the ${1}$ branch the same guard fires, pruning ${1, 2}^{'}$ . But descending from ${2}$ to ${2, 2}$ is ancestor reuse, not a sibling repeat — there $i = s t a r t$ , the guard does not fire, and both copies of $2$ are legitimately used.

This same machinery distinguishes two classic problems. In Combination Sum, each number may be reused unboundedly, so after choosing $a_{i}$ we recurse with start = i (do not advance); staying on the same element keeps it available. In Combination Sum II, each input number may be used at most once and duplicates exist, so we recurse with start = i+1 (advance) and apply the equal-sibling skip above to avoid duplicate combinations.

The one-line difference: reuse-allowed recurses with

s t a r t = i

(stay), use-once recurses with

s t a r t = i + 1

(advance)

subsets.pypython

from typing import Sequence, TypeVar
from comparable import Comparable


Element = TypeVar("Element", bound=Comparable)


def subsets_with_duplicates(
  elements: Sequence[Element],
) -> list[list[Element]]:
  """
    Every distinct subset of a multiset such as [1, 2, 2].\n
    Sort, then at each level skip a choice equal to the one just tried at the\n
    same depth (`index > start and a[index] == a[index - 1]`), which drops\n
    identical sibling subtrees without losing a distinct solution.\n
  """
  ordered: list[Element] = sorted(elements)
  size: int = len(ordered)
  results: list[list[Element]] = []
  partial: list[Element] = []

  def explore(start: int) -> None:

    # every node is a subset.
    results.append(list(partial))

    for index in range(start, size):

      # skip a repeated value among siblings at this same depth.
      if index > start and ordered[index] == ordered[index - 1]:
        continue

      # take this value, recurse forward, then drop it.
      partial.append(ordered[index])
      explore(index + 1)
      partial.pop()

  explore(0)
  return results

comparable.pypython

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

Pruning: kill infeasible subtrees early

Everything so far enumerates all of a space. Backtracking becomes useful when the problem constrains the answer, because then we can prune: refuse to descend into a subtree the moment we can prove it contains no solution. Pruning prunes whole subtrees, so a single early cut can save exponentially many leaves. A prune is sound precisely when it only ever cuts subtrees that provably hold no solution; both cuts below qualify, so the search stays complete — no real solution is lost.

Take Combination Sum with a target $T$ over sorted positive numbers. Two prunes apply at the point we consider extending partial (current sum $s$ ) by $a_{i}$ :

Over-target cut. If $s + a_{i} > T$ , this choice overshoots; and since the array is sorted ascending, every later $a_{j} \geq a_{i}$ overshoots too, so we break out of the entire loop, not merely continue.
Reachability cut (a general lower-bound prune). If even the smallest remaining additions cannot reach $T$ , abandon the branch.

Pruning kills infeasible subtrees early (target

T = 5

, choices

{2, 3, 4}

)

Each branch reaching $s > 5$ (the dashed $\times$ nodes) is dropped without descending further; the blue path $0 \to 2 \to 5$ is the live solution ${2, 3}$ . Pruning determines the practical cost: a search that looks exponential can run in milliseconds when the prune severs the bulk of the tree, while a poorly pruned search of the same size is hopeless. This is why Skiena frames practical combinatorial search as the art of pruning.²

To see how much the prune saves, trace Combination Sum with target $T = 7$ on the sorted candidates $[2, 3, 6, 7]$ , each reusable. The recursion carries the running sum $s$ and a start index; the over-target cut breaks the loop the moment $s + a_{i} > T$ (safe because later candidates are only larger).

Path so far	$s$	tries $a_{i}$	outcome
$[]$	0	$2$	descend
$[2]$	2	$2$	descend
$[2, 2]$	4	$2$	descend
$[2, 2, 2]$	6	$2 : 8 > 7$	break (also $3, 6, 7$ skipped)
$[2, 2, 3]$	7	—	record ${2, 2, 3}$
$[2, 3]$	5	$3 : 8 > 7$	break
$[2, 6]$	8	overshoot at entry	pruned
$[3]$	3	$3$	descend
$[3, 3]$	6	$3 : 9 > 7$	break
$[7]$	7	—	record ${7}$

The two solutions ${2, 2, 3}$ and ${7}$ are found while the over-target break lops off every branch that would push $s$ past $7$ — the subtrees under $[2, 2, 2]$ , $[2, 6]$ , $[3, 3]$ , and the whole $[6, \dots]$ region never materialize. Without the sorted-break prune the same search would blindly expand all of them before discovering they overshoot.

combination_sum.pypython

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:
  """
    Every combination of `candidates` summing to `target`, where each number\n
    may be reused unboundedly. After choosing index `i`, recurse with\n
    start = i so the same element stays available.\n
  """
  ordered: list[int] = sorted(candidates)
  size: int = len(ordered)
  results: list[list[int]] = []
  partial: list[int] = []

  def explore(start: int, remaining: int) -> None:
    if remaining == 0:
      results.append(list(partial))
      return
    for index in range(start, size):
      value: int = ordered[index]

      # over-target cut: ascending order means every later value overshoots
      # too, so abandon the whole rest of the loop.
      if value > remaining:
        break

      # take this value and recurse with start = index so it stays available.
      partial.append(value)
      explore(index, remaining - value)
      partial.pop()

  explore(0, target)
  return results

def combination_sum_unique(
  candidates: list[int],
  target: int,
) -> list[list[int]]:
  """
    Every distinct combination of `candidates` summing to `target`, where\n
    each input number may be used at most once. After choosing index `i`,\n
    recurse with start = i + 1, and skip an equal sibling at the same depth\n
    (`index > start and a[index] == a[index - 1]`) to drop duplicates.\n
  """
  ordered: list[int] = sorted(candidates)
  size: int = len(ordered)
  results: list[list[int]] = []
  partial: list[int] = []

  def explore(start: int, remaining: int) -> None:
    if remaining == 0:
      results.append(list(partial))
      return
    for index in range(start, size):
      value: int = ordered[index]

      # over-target cut: ascending order means every later value overshoots.
      if value > remaining:
        break

      # skip a repeated value among siblings at this same depth.
      if index > start and ordered[index] == ordered[index - 1]:
        continue

      # take this value and recurse with start = index + 1 so it is used once.
      partial.append(value)
      explore(index + 1, remaining - value)
      partial.pop()

  explore(0, target)
  return results

generate_parentheses.pypython

def generate_parentheses(pairs: int) -> list[str]:
  """
    Every well-formed string of `pairs` pairs of parentheses.\n
    `opened` counts opens placed so far; `closed` counts closes. We open\n
    while opened < pairs, and close only while closed < opened.\n
  """
  results: list[str] = []
  partial: list[str] = []

  def explore(opened: int, closed: int) -> None:
    if len(partial) == 2 * pairs:
      results.append("".join(partial))
      return

    # open a bracket while opens remain.
    if opened < pairs:
      partial.append("(")
      explore(opened + 1, closed)
      partial.pop()

    # close a bracket only while an unmatched open is available — the prune
    # that forbids ever building an invalid prefix.
    if closed < opened:
      partial.append(")")
      explore(opened, closed + 1)
      partial.pop()

  explore(0, 0)
  return results

Complexity: the size of the explored tree

There is no single formula for backtracking complexity; the running time is simply the size of the state-space tree we actually explore, times the work per node. For a full enumeration this is the output size: $Θ (n \cdot 2^{n})$ for subsets, $Θ (n \cdot n!)$ for permutations, $Θ (k (k n))$ for combinations. More generally the cost is $O (# nodes visited \times cost per node)$ , and for problems whose answers we emit, it is bounded below by $Ω (# solutions \times size of each)$ : we cannot beat the cost of writing the output.

The lever is always the same: a tighter $Prune$ predicate cuts subtrees nearer the root, and the savings compound exponentially with the depth of the cut.

From a 1965 method to modern industrial solvers

The choose/explore/un-choose skeleton is the direct ancestor of some of the most widely used software in computing.

Naming the method. The recursive-abandonment idea is old — the term backtrack was coined by D. H. Lehmer in the 1950s — but Golomb and Baumert's 1965 paper Backtrack Programming was the first systematic treatment, and it already identified the two levers this lesson emphasizes: preclusion (pruning) and choosing which variable to branch on next.⁴ Every refinement since is a sharper answer to those two questions.

Dancing Links. For exact-cover problems (Sudoku, pentomino tiling, $n$ -queens), Knuth's Algorithm X with the Dancing Links data structure (2000) makes the choose/un-choose pair almost free: the constraint matrix is a doubly-linked mesh, covering a column unlinks its rows in $O (1)$ , and un-covering relinks them by running the same pointer operations backward — the un-choose step made literal.⁵ It remains the fastest general exact-cover solver and the reason a Sudoku solves in microseconds.

SAT solvers. Boolean satisfiability is backtracking's largest application. The DPLL algorithm (Davis, Putnam, Logemann, Loveland, 1962) is backtracking over truth assignments with unit propagation — a constraint-propagation prune. Its modern descendant, CDCL (conflict-driven clause learning), adds two ideas that transform the search: when a branch fails, it analyzes the conflict to learn a new clause that prunes many future branches, and it non-chronologically backjumps past irrelevant decisions rather than backtracking one level at a time.⁶ CDCL solvers routinely dispatch formulas with millions of variables, and are used in hardware verification, program analysis, and automated planning — all built on the recursion of this lesson.

Takeaways

Backtracking is depth-first search of a state-space tree: build a partial solution incrementally, and abandon any branch that cannot reach a valid complete solution.
The universal template is choose / explore / un-choose: a single mutable buffer suffices because the undo step restores it before each sibling is tried.
Subsets ( $2^{n}$ ) come from an include/exclude binary recursion or a forward-only start index; permutations ( $n!$ ) from a used[] array or in-place swapping; combinations ( $(k n)$ ) from a start index that forces increasing choices so each set is generated once.
Duplicates are handled by sorting and skipping equal siblings at the same depth (if i > start and a[i] == a[i-1] continue), which drops identical subtrees without losing distinct solutions; reuse-allowed variants keep start = i instead of advancing.
Pruning, cutting infeasible or non-improving subtrees early (sum exceeds target, bound can't beat the best), is what separates exponential-but-fast from hopeless; one early cut saves an exponential subtree.
Running time is the size of the explored tree times per-node work: exponential in the worst case, but tamed to practicality by good pruning on typical inputs.

Erickson, Ch. — Backtracking: incrementally constructing a solution and abandoning partial candidates that cannot be completed. ↩
Skiena, §7 — Combinatorial Search and Heuristic Methods: the state-space search tree and pruning as the core of efficient exhaustive search. ↩ ↩²
CLRS, Ch. — Exhaustive Search: backtracking explores only feasible extensions, exponential in the worst case but far smaller in practice. ↩
Golomb, S. W. & Baumert, L. D. (1965), Backtrack programming, Journal of the ACM 12(4), 516–524 — the first systematic study of backtracking, naming preclusion (pruning) and variable ordering as the two levers of efficiency. ↩
Knuth, D. E. (2000), Dancing links, in Millennium Perspectives in Computer Science, 187–214 — Algorithm X with the doubly-linked Dancing Links structure making cover/uncover (choose/un-choose) $O (1)$ and reversible. ↩
Marques-Silva, J. P. & Sakallah, K. A. (1999), GRASP: a search algorithm for propositional satisfiability, IEEE Transactions on Computers 48(5), 506–521 — conflict-driven clause learning and non-chronological backjumping, extending the DPLL backtracking search (Davis, Logemann & Loveland, 1962) into modern industrial SAT solvers. ↩

The paradigm: choose, explore, un-choose

Subsets: the power set in 2n

Permutations: n! orderings

Combinations: (kn​) with a start index

Handling duplicates: skip equal siblings

Pruning: kill infeasible subtrees early

Complexity: the size of the explored tree

From a 1965 method to modern industrial solvers

Takeaways

Footnotes

Subsets: the power set in $2^{n}$

Permutations: $n!$ orderings

Combinations: $(k n)$ with a start index