224: Backtracking: Decision Trees, Pruning, Permutations, Combinations, and Constraint Search

Learning outcomes

By the end of this lesson, you can:

explain and apply choose explore unchoose in a realistic implementation;
explain and apply decision tree in a realistic implementation;
explain and apply pruning in a realistic implementation;
explain and apply permutation deduplication in a realistic implementation;
explain and apply constraint propagation in a realistic implementation.

These are not five unrelated tricks. They are ways to make a search over possible decisions explicit, bounded, and testable. You should be able to describe what a search node represents, why a branch is legal, when it can stop, and what state must be restored before the next branch begins.

Prerequisites and retrieval

This lesson assumes the earlier 01–06 foundation and the preceding lessons in this module. Before reading, retrieve one concrete example from a previous project where the same concern appeared. Perhaps you generated combinations, retried work, validated a partially built object, or had to reject an option as soon as it violated a rule. The point is not to memorize a backtracking template. It is to make a defensible choice in both an interview-sized problem and a production data-processing problem, reasoning from constraints instead of from a familiar pattern.

Terminology

Choose explore unchoose: Extend or mutate the current candidate, recurse into the resulting state, then restore that state before trying the next choice. The restoration step is what prevents one branch's choices from leaking into its siblings.
Decision tree: A model of the search in which each node is a partial candidate and each outgoing edge is one possible next decision. Branching factor and depth determine the worst-case exponential growth.
Pruning: Stop exploring a branch as soon as its partial candidate cannot lead to a valid or better complete solution. A branch that is already impossible has no value as future work.
Permutation deduplication: When input values repeat, sorting plus “skip equal unused sibling choices,” or generating from a frequency map, prevents duplicate permutations from entering the output.
Constraint propagation: Sudoku- and N-Queens-like problems become more manageable when sets or bitmasks track occupied rows, columns, boxes, or diagonals. Those structures make feasibility checks O(1) and can expose the most constrained next variable.
Output-sensitive cost: If the problem asks for every valid solution, the runtime must at least scale with the amount of output. Complexity must include the cost of copying or materializing each solution, not just the number of recursive calls.

Mental model

Treat Backtracking: Decision Trees, Pruning, Permutations, Combinations, and Constraint Search as a design problem with observable inputs, outputs, invariants, and failure modes. Backtracking enumerates a decision tree while undoing choices. A reliable implementation makes the candidate state, feasibility test, termination condition, deduplication rule, and pruning rule explicit.

For example, in a permutation search, the current path is the prefix already selected and the remaining values are the choices still available. The invariant might be “the path contains no value more times than the input contains it.” In N-Queens, the invariant is stronger: no two placed queens share a column or diagonal. These statements are more useful than saying only that the function is “recursive,” because they tell you exactly what to inspect when a result is wrong.

A strong implementation also makes assumptions visible, narrows uncertainty at boundaries, and leaves enough evidence—tests, types, constraints, metrics, or diagrams—to explain why the design is safe. The recursion is only the control flow; the real algorithm is the state model plus the rules that govern each transition.

A useful interview and production sequence is:

requirement -> constraints -> model -> implementation -> failure analysis -> verification

Do not jump from a requirement directly to a library call or a memorized recursive skeleton. First state what must remain true. Then choose the mechanism that enforces it. For an “all solutions” problem, also clarify whether order matters, whether duplicate values are distinct, whether solutions may be returned lazily, and what input size is credible.

Deep dive

1. Choose explore unchoose

The basic operation is simple: make one choice, explore everything that follows from it, and undo the choice before considering the next one. A path array is commonly mutated with push, passed through the recursive call, and restored with pop. A set of used values may be updated and then cleared in the same way.

The last step is not cleanup that can be omitted. Shared mutable state represents the current branch. If it is not restored, the next sibling branch starts with facts that belong to the previous branch and produces missing or invalid results. This is one of the most common backtracking bugs.

Decision rule: Use choose explore unchoose deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Copying state at each call can be easier to reason about, but it trades clarity about mutation for additional allocation and copying.

2. Decision tree

The decision tree gives recursion a concrete shape. Each node is a partial candidate; each edge is a legal choice from that point; each leaf is either a complete answer or a dead end. Drawing the first few levels for a small n often reveals that the algorithm is exploring more than the problem requires, or that two branches describe the same state.

If the branching factor is approximately b and the depth is d, the number of nodes can be on the order of b^d in the worst case. Permutations commonly have shrinking branching factor and therefore n! leaves. The exact bound depends on the choices and constraints, but the tree makes the source of the cost visible.

Decision rule: Use the decision-tree model deliberately when it makes the contract or invariant easier to prove. If it only gives a recursive shape while hiding duplicate or symmetric states, draw and label the states more explicitly before coding.

3. Pruning

Pruning means refusing to recurse once a partial candidate cannot produce a valid or better complete solution. In a combination whose sum has already exceeded the target, continuing is pointless when all remaining values are non-negative. In a constrained placement problem, a row, column, or diagonal conflict can reject the branch immediately.

The pruning condition must be justified by the problem's constraints. A rule that is valid for sorted positive values may be wrong when negative values are allowed or when order affects the result. Strong pruning can change an impractical enumeration into a usable search for constrained n, but it does not make the general worst case disappear.

Decision rule: Use pruning deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Test the boundary where pruning should and should not occur; an over-aggressive condition silently removes valid answers.

4. Permutation deduplication

With repeated input values, choosing by array index can create identical value sequences through different index paths. For input [1, 1, 2], the two 1 positions are distinct to the implementation but indistinguishable in the requested output. Returning both copies is a correctness bug, not merely an efficiency issue.

The common approach is to sort first, then skip a value when it equals the previous value at the same recursion depth and that previous equal value has not been used in the current path. The “same depth” qualification matters: equal values may still be selected at different positions in one permutation. A frequency map is another sound option; it chooses a value only while its remaining count is positive, then restores the count after recursion.

Decision rule: Use permutation deduplication deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. State whether the output is unique by value or by input identity before choosing the rule.

5. Constraint propagation

Constraint search becomes faster when each choice updates the information used to reject future choices. For N-Queens, sets can track occupied columns and the two diagonal keys, row - column and row + column. A candidate square is feasible if none of those keys is already occupied. With sets or bitmasks, that test is O(1) rather than scanning all previously placed queens.

The same idea applies to Sudoku: maintain candidate information for rows, columns, and boxes, remove a chosen value from affected peers, and select an empty cell with fewest remaining candidates. Choosing the most constrained variable first often reduces the tree substantially because contradictions appear earlier. This is a search-order heuristic, so it must remain consistent with the solution contract and be measured rather than assumed to help every input.

Decision rule: Use constraint propagation deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Keep the source of truth for each constraint clear so that placement and undo operations update matching structures.

6. Output-sensitive cost

When the requirement is “return all valid solutions,” no algorithm can avoid spending time to produce those solutions. If there are S solutions and each contains L values, merely materializing the output costs at least O(S * L) time and storage for the returned data. Recursive call counts alone are therefore an incomplete complexity statement.

The search itself may take exponential or factorial time, while the output copy adds another factor related to solution length. If callers can consume answers one at a time, a generator can reduce peak output storage, but it does not remove the work required to enumerate the answers. State both costs and distinguish auxiliary recursion state from the output.

Decision rule: Use output-sensitive cost deliberately when it makes the contract or invariant easier to prove. If it only reduces typing while hiding an assumption, prefer the more explicit design. Explain which bound describes the search tree and which describes the results the caller requested.

Worked example

Consider an interview-sized problem and a production data-processing problem, so the learner must reason from constraints rather than memorize a template. Start by writing the requirement in one sentence, listing the input and output contracts, and assigning each failure mode to the concept that owns it. For a search problem, specify whether the function returns one answer or all answers, whether ordering matters, and whether duplicate values should produce duplicate outputs.

The important architectural separation is the same one used outside algorithms: parsing or validation belongs at the boundary; domain rules belong in the domain or service layer; persistence rules belong in the database or repository; presentation rules belong in the client. Mixing these concerns can make a happy-path demo look shorter, but it makes edge cases, retries, and malformed data much harder to reason about.

The following small function is not a backtracking implementation. It is a deliberately simple reminder that the state invariant should be stated before choosing a data structure. Here, answer is always the greatest value seen so far.

function solve(values: readonly number[]): number {
  let answer = 0;
  // State the invariant before choosing the data structure.
  for (const value of values) {
    answer = Math.max(answer, value);
  }
  return answer;
}

There is an edge case hidden in this example: initializing answer to 0 is only correct if the input contract guarantees that the intended result cannot be below zero and that an empty array has a defined result of 0. If negative values or empty input are valid, the contract needs to change, for example by rejecting empty input or initializing from the first element. The same discipline applies to backtracking: state the empty-input behavior and the validity assumptions before writing the base case.

Walk the example with at least four cases: the normal path, an empty or missing value, a duplicate/retry/concurrent path where relevant, and a dependency failure. For each case, state which layer detects the problem and what the caller observes. In an algorithm implementation, translate those cases into tests for the smallest input, duplicate choices, an already-invalid partial candidate, and the largest credible input. This is the level of explanation expected in a senior code review or technical interview.

Production perspective

Production correctness is broader than “the code works on my machine.” Ask how the design behaves during deploys, retries, partial failure, stale clients, concurrent requests, malformed data, schema changes, and high cardinality. Backtracking can consume CPU, stack depth, and memory unexpectedly when input grows, so establish credible limits and reject or bound work before a request can monopolize a process.

Prefer explicit contracts, bounded resource usage, structured errors, and measurable behavior. Count search nodes, pruned branches, maximum depth, and output size when those measurements help explain a performance problem. Optimize only after you can identify the bottleneck or risk with evidence.

When the topic involves an external dependency, define a timeout and cancellation strategy. When it involves persistence, define transaction and consistency expectations. When it involves user-visible state, define loading, empty, error, stale, and success states. When it involves security, assume the client can be modified and network input is untrusted. A client-provided “solution” or constraint must be validated again on the owning server or domain boundary.

Guided lab

Implement permutations with duplicates and N-Queens or Sudoku. Add pruning and compare node counts before and after; state complexity in terms of the search tree and output size. For permutations, verify that repeated values produce unique value sequences. For N-Queens or Sudoku, verify that every returned arrangement satisfies every constraint, not only that the search terminates.

Complete the lab with this discipline:

Write the requirement and two non-requirements.
List input, output, and error contracts before implementation.
Implement the smallest correct vertical slice.
Add at least one invalid-input test and one edge-case test.
Instrument or inspect the behavior instead of guessing.
Refactor one hidden assumption into an explicit type, constraint, function, or configuration.
Explain one alternative design and why you did not choose it.
Record a short “what would break at 10× scale?” note.

The comparison is part of the lab, not optional decoration. Record how many nodes the unpruned search visits, how many the pruned version visits, and how much output is actually produced. A lower node count is useful only if the pruning rule is still complete and does not remove valid solutions.

Edge cases and failure modes

Choose explore unchoose: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Specifically verify that state after returning from one branch matches the state before that branch was chosen.
Decision tree: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Draw a small tree and check that every legal branch is represented exactly as intended.
Pruning: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include a case exactly at the pruning boundary and a case that would be incorrectly removed by a too-strong assumption.
Permutation deduplication: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Include all-equal values, no duplicates, and duplicates at different recursion depths.
Constraint propagation: Test absence, malformed input, duplicates, ordering/concurrency where applicable, and behavior at the smallest and largest credible sizes. Verify that every placement updates its row, column, and diagonal or peer structures and that undo restores all of them.

Common mistakes and debugging

Solving the example instead of the requirement: a copied pattern can be syntactically correct but architecturally wrong. Confirm whether the caller wants one result, all results, unique results, or a count.
Hiding uncertainty with assertions, broad exception handlers, permissive schemas, or “temporary” any values. Make input and output contracts explicit at the boundary.
Testing only the happy path and therefore discovering contracts only after integration. Include empty, malformed, duplicate, contradictory, and maximum credible inputs.
Optimizing before measuring, or selecting a scalable mechanism without a scale requirement. Measure node counts, output size, allocations, and runtime before changing the search.
Letting client-side behavior stand in for server-side authorization, validation, or persistence guarantees. Untrusted input must be checked by the layer that owns the rule.

For debugging, reproduce the smallest failing case, inspect the actual candidate path and constraint sets, trace the boundary where the invariant first becomes false, and fix the owning layer rather than adding a downstream patch. Log or assert state at the choice, recursive return, and unchoose points. If a result is missing, inspect pruning and deduplication first; if a result is invalid, inspect state restoration and constraint updates.

Interview questions

What problem does Choose explore unchoose solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Decision tree solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Pruning solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Permutation deduplication solve, and what trade-off or failure mode would make you choose a different approach?
What problem does Constraint propagation solve, and what trade-off or failure mode would make you choose a different approach?

When answering, do more than name a technique. State the candidate state, the invariant, the base case, the condition that rejects a branch, and the part of the complexity that comes from materializing output. That explanation demonstrates understanding better than reproducing a recursive loop from memory.

Checkpoint

Without notes, explain Backtracking: Decision Trees, Pruning, Permutations, Combinations, and Constraint Search to another developer in five minutes. Your explanation must include one invariant, one edge case, one production failure mode, and one alternative design. Then implement a small example without copying the lesson code.

As a final check, be able to explain why each branch is legal, why the base case is complete, and why the undo operation restores the caller's state. If you cannot answer one of those questions, the implementation is not yet ready for review.

Mastery checklist

I can define the core terms precisely.
I can choose a design from requirements instead of from habit.
I can implement and test the normal path and edge cases.
I can explain the runtime, storage, or complexity cost.
I can identify which layer owns validation, errors, and recovery.
I can compare at least two reasonable alternatives.
I can explain how the design changes at larger scale or stricter reliability.