i. Backtracking and Pruning

Brute Force

Enumerate every candidate and check it. The first solution to write for any problem: it is the reference for stress testing, it reveals patterns on small inputs, and it is the full solution when the constraints allow.

What can be enumerated in ~1 second

Object	Count	Feasible $n$
subsets	$2^n$	$n\le 25$ (with $O(1)$ work), $n\le 20$ (with $O(n)$)
permutations	$n!$	$n\le 10$ ($11$ with $O(1)$ work)
pairs / triples	$n^2$ / $n^3$	$n\le 10^4$ / $n\le 500$
subsets of size $k$	$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$	check the number, $\left(\genfrac{}{}{0ex}{}{30}{15}\right)\approx 1.5\cdot 10^8$
strings over $\Sigma$	$|\Sigma {|}^n$	$26^5\approx 1.2\cdot 10^7$
divisors of $n$	$d(n)\le 1344$ for $n\le 10^9$	always
partitions of $n$	$p(n)$	$p(50)\approx 2\cdot 10^5$, $p(80)\approx 1.6\cdot 10^7$

Enumeration templates

// all subsets
for (int mask = 0; mask < (1 << n); mask++) { /* bit i set => take a[i] */ }
 
// all permutations (start from sorted to get all)
sort(p.begin(), p.end());
do { /* use p */ } while (next_permutation(p.begin(), p.end()));
 
// all k-subsets (Gosper)
for (int s = (1 << k) - 1; s < (1 << n); ) {
    /* use s */
    int c = s & -s, r = s + c; s = (((r ^ s) >> 2) / c) | r;
}
 
// recursion over choices with pruning -> backtracking

Smarter brute force

• Enumerate the answer instead of the input: “is the answer $\le 60$?” then try each.
• Enumerate one variable, compute the other: $a+b=s$ fixes $b$.
• Meet in the middle: split into halves of $2^{n/2}$.
• Symmetry breaking: fix the first element, sort to avoid duplicates.
• Pruning: stop when the partial cost already exceeds the best (branch and bound).

Brute force as a tool

1. Print the answers for $n=\mathrm{1..10}$ and search the sequence (OEIS-style pattern finding).
2. Stress-test the main solution against it with random small inputs.
3. Verify a greedy rule on all small cases before proving it.

Pitfalls

• Count the operations: $2^{20}\cdot 20=2\cdot 10^7$ is fine, $2^{25}\cdot 25\approx 8\cdot 10^8$ is borderline.
• next_permutation skips permutations if you start from an unsorted array.

Backtracking

Build a solution incrementally; abandon a partial solution (“backtrack”) as soon as it cannot be completed.

The skeleton

void solve(State& s, int depth) {
    if (complete(s)) { record(s); return; }
    if (!feasible(s)) return;                          // PRUNE
    for (Choice c : candidates(s)) {
        apply(s, c);
        solve(s, depth + 1);
        undo(s, c);                                    // the "backtrack"
    }
}

The undo is what makes it backtracking rather than brute force: state is mutated in place and restored, so no copying is needed.

Proof: backtracking is complete and sound

Soundness (never reports an invalid solution): record is only called when complete(s) holds, and s is built by a sequence of apply calls, each a legal move by construction of candidates, so every recorded state is a genuinely reachable, complete configuration. Completeness (every valid solution is eventually found, when nothing is pruned): the recursion explores every choice in candidates(s) at every reachable state, so by induction on depth it visits every sequence of choices reachable from the start — exactly the full state space, restricted only by the explicit feasible prune. Pruning preserves completeness for the intended question (“does a solution exist / what is the best one”) exactly when feasible is safe: it must only return false for states that provably cannot be completed into a valid (or, for optimisation, a better-than-incumbent) solution — then no reachable solution is ever skipped, only dead branches are. $■$

Pruning — where all the performance is

Without pruning, backtracking is just exponential enumeration. The techniques, in rough order of value:

Technique	Idea
Constraint propagation	after each choice, eliminate now-impossible options
Most-constrained variable first (MRV)	branch on the variable with the fewest remaining options
Least-constraining value	try the value that eliminates the fewest options for others
Bounding	if the best possible completion is worse than the incumbent, prune
Symmetry breaking	fix a canonical order among interchangeable choices
Forward checking	detect a variable with zero remaining options immediately
Memoization	cache equivalent states
Early failure detection	check global feasibility (counts, parity, connectivity)

MRV is the single highest-value heuristic. Branching on the most constrained variable makes the tree narrow at the top, where it matters most. It is what turns a Sudoku solver from seconds to microseconds.

Symmetry breaking

If items are interchangeable, fix a canonical order so each solution is generated once:

// assigning items to groups: item i may only open group g if all groups < g are used
for (int g = 0; g <= usedGroups && g < maxGroups; g++) { ... }

Without this, a partition into $k$ groups is produced $k!$ times. This is often a 10-100× speedup and is the first thing to add.

Proof: this symmetry break loses no solutions

Any assignment of items to $k$ interchangeable groups can be relabelled (permute the group indices) into a canonical form where group $g$ is only opened after groups $0,\dots ,g-1$ have each received at least one item — i.e. the first item to open a new group always opens the lowest-numbered unused group. Since relabelling groups doesn’t change the partition itself (groups are interchangeable by assumption), every distinct partition has exactly one representative satisfying this rule, and the restricted loop (g <= usedGroups) generates exactly those canonical representatives — one per partition, not $k!$.

Other common symmetries: reflections and rotations of a board, permutations of identical pieces, and the choice of which element goes “first”.

Classic backtracking problems

Problem	Key pruning
N-Queens	column/diagonal bitmasks; place row by row
Sudoku	MRV + constraint propagation, or DLX
Graph colouring	order vertices by degree; symmetry-break the colours
Knight’s tour	Warnsdorff’s rule (fewest onward moves first)
Subset sum / partition	sort descending; skip duplicates; bound the remaining sum
Hamiltonian path	prune on degree-0 or two degree-1 vertices remaining
Exact cover (pentominoes)	Dancing Links
Crossword / word placement	MRV on the most constrained slot
Maximum clique	Bron-Kerbosch with a colouring bound

N-Queens with bitmasks

void queens(int row, int cols, int d1, int d2, int n, int& count) {
    if (row == n) { count++; return; }
    int avail = ~(cols | d1 | d2) & ((1 << n) - 1);
    while (avail) {
        int bit = avail & -avail;
        avail ^= bit;
        queens(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1, n, count);
    }
}

Three integers encode all the constraints, and the shifts propagate the diagonals automatically. $n=15$ in well under a second. (Proof that the shifts correctly track the diagonals: N-Queens, below, where this is the main algorithm.)

Warnsdorff’s rule

For a knight’s tour, always move to the square with the fewest onward moves. This heuristic finds a tour on boards up to $100\times 100$ almost without backtracking — a striking demonstration that a good ordering can dominate everything else.

Skipping duplicates

When the candidate list contains equal values, generate each distinct choice once:

sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
    if (i > 0 && a[i] == a[i-1] && !used[i-1]) continue;    // skip duplicates
    ...
}

The !used[i-1] condition forces equal elements to be used in index order. This is the standard idiom for “permutations with duplicates” and “subsets with duplicates”.

Backtracking vs the alternatives

Situation	Method
Small $n$, need all solutions	backtracking
Small $n$, need one solution	backtracking with early exit
Optimising, with a good bound	branch and bound
Overlapping subproblems	memoization / DP
$n\le 22$, subset structure	bitmask DP
$n\le 45$, splittable	meet in the middle
Exact cover structure	Dancing Links
Boolean constraints	a SAT solver, or 2-SAT if binary clauses
Too big for exact	heuristics

Pruning

Idea and use

Skip a search branch only when it cannot contain a feasible or better answer.

Method and cost

Use infeasibility checks, admissible objective bounds, symmetry breaking, and dominance. For maximizing clique size, prune when current_size+candidate_count<=best; a proper coloring of candidates gives a tighter upper bound.

Correctness and pitfalls

Heuristic move ordering is safe, but heuristic rejection may lose the optimum. If an incumbent equals a bound, pruning depends on whether every optimal witness or only one is needed.

Work it out

Design a lower bound for bin packing from remaining total size and test that it never exceeds the true optimum on tiny inputs.

Backtracking Puzzles

Bitmask Sudoku solver, Warnsdorff knight’s tour, counting simple paths in a grid maze, and word search on a letter grid.

bool ok = solveSudoku(g);                 // g: 9 strings of 9 chars, '.' or '0' for empty; filled in place
auto tour = knightsTour(n, sr, sc);       // n x n board, order[r][c] = move number, {} if none found
i64 p = countMazePaths(grid);             // simple paths from (0,0) to (n-1,m-1) through '.', 4 directions
bool w = wordSearch(grid, word);          // adjacent cells, each used at most once

Complexity: exponential in the worst case; Sudoku solves hard instances in milliseconds (most constrained cell first + bitmasks); Warnsdorff is linear per attempt and almost always succeeds for $n\ge 5$.
Pruning order matters more than anything: pick the variable with the fewest options, keep candidate sets as bitmasks, undo changes on return.

Proof: these four solvers are correct

solveSudoku. This is plain backtracking (try each legal digit in an empty cell, recurse, undo on failure) with one search-order choice: always branch on the cell with the fewest candidates (MRV). MRV changes only the order branches are tried in, never which branches exist, so it cannot change correctness — soundness (every returned grid satisfies all constraints, tracked exactly by row/col/box bitmasks, checked incrementally) and completeness (every legal digit at the chosen cell is tried; bestCnt==0 correctly reports immediate failure when some empty cell has no legal digit left) hold exactly as for the naive order, and choosing the most-constrained cell first only prunes the search tree shape to fail fast, not the set of solutions considered.
countMazePaths. Marking cells visited and unmarking on return (the backtracking undo) ensures each recursive call explores only simple paths (no revisited cell), and the recursion tries all 4 neighbours from every cell — so by induction on remaining path length, every simple path from the current cell to the target is eventually tried exactly once, and count accumulates exactly the number of simple paths from $(0,0)$ to $(n-1,m-1)$.
wordSearch. Identical argument: temporarily marking the current cell '#' (so it cannot be reused later in the same attempt) and restoring it on return means every candidate path spelling out word letter-by-letter, using each board cell at most once per attempt, is explored; the function returns true as soon as any starting cell leads to a complete match, and false only once every starting cell and every branch from it has been exhausted without success. $■$

Implementation

bool solveSudoku(vector<string>& g) {
    array<int, 9> row{}, col{}, box{};
    vector<pair<int, int>> empty;
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) {
            if (g[r][c] == '.' || g[r][c] == '0') {
                g[r][c] = '.';
                empty.push_back({r, c});
                continue;
            }
            int bit = 1 << (g[r][c] - '1');
            if ((row[r] | col[c] | box[r / 3 * 3 + c / 3]) & bit) return false;
            row[r] |= bit, col[c] |= bit, box[r / 3 * 3 + c / 3] |= bit;
        }
    }
    auto dfs = [&](auto&& self, int left) -> bool {
        if (left == 0) return true;
        int best = -1, bestCnt = 10, bestMask = 0;
        for (int i = 0; i < left; i++) {   // most constrained empty cell
            auto [r, c] = empty[i];
            int mask = ~(row[r] | col[c] | box[r / 3 * 3 + c / 3]) & 511, cnt = __builtin_popcount(mask);
            if (cnt < bestCnt) best = i, bestCnt = cnt, bestMask = mask;
        }
        if (bestCnt == 0) return false;
        swap(empty[best], empty[left - 1]);
        auto [r, c] = empty[left - 1];
        for (int m = bestMask; m; m &= m - 1) {
            int bit = m & -m;
            row[r] |= bit, col[c] |= bit, box[r / 3 * 3 + c / 3] |= bit;
            g[r][c] = char('1' + __builtin_ctz(bit));
            if (self(self, left - 1)) return true;
            row[r] ^= bit, col[c] ^= bit, box[r / 3 * 3 + c / 3] ^= bit;
        }
        g[r][c] = '.';
        swap(empty[best], empty[left - 1]);
        return false;
    };
    return dfs(dfs, empty.size());
}
 
vector<vector<int>> knightsTour(int n, int sr, int sc) {
    const int dr[] = {1, 2, 2, 1, -1, -2, -2, -1}, dc[] = {2, 1, -1, -2, -2, -1, 1, 2};
    for (int attempt = 0; attempt < 8; attempt++) {   // rotate the tie-break order on failure
        vector<vector<int>> order(n, vector<int>(n, -1));
        int r = sr, c = sc;
        order[r][c] = 0;
        auto degree = [&](int x, int y) {
            int d = 0;
            for (int k = 0; k < 8; k++) {
                int nx = x + dr[k], ny = y + dc[k];
                d += nx >= 0 && ny >= 0 && nx < n && ny < n && order[nx][ny] == -1;
            }
            return d;
        };
        bool ok = true;
        for (int step = 1; step < n * n && ok; step++) {
            int best = -1, bestDeg = 9;
            for (int t = 0; t < 8; t++) {
                int k = (t + attempt) % 8, nx = r + dr[k], ny = c + dc[k];
                if (nx < 0 || ny < 0 || nx >= n || ny >= n || order[nx][ny] != -1) continue;
                int d = degree(nx, ny);
                if (d < bestDeg) bestDeg = d, best = k;
            }
            if (best == -1) ok = false;
            else r += dr[best], c += dc[best], order[r][c] = step;
        }
        if (ok) return order;
    }
    return {};
}
 
i64 countMazePaths(const vector<string>& grid) {
    int n = grid.size(), m = grid[0].size();
    vector<vector<char>> used(n, vector<char>(m, 0));
    i64 count = 0;
    auto dfs = [&](auto&& self, int r, int c) -> void {
        if (r == n - 1 && c == m - 1) {
            count++;
            return;
        }
        used[r][c] = 1;
        const int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr >= 0 && nc >= 0 && nr < n && nc < m && grid[nr][nc] == '.' && !used[nr][nc]) self(self, nr, nc);
        }
        used[r][c] = 0;
    };
    if (grid[0][0] == '.' && grid[n - 1][m - 1] == '.') dfs(dfs, 0, 0);
    return count;
}
 
bool wordSearch(vector<string> grid, const string& word) {
    int n = grid.size(), m = grid[0].size();
    auto dfs = [&](auto&& self, int r, int c, int i) -> bool {
        if (i == (int)word.size()) return true;
        if (r < 0 || c < 0 || r >= n || c >= m || grid[r][c] != word[i]) return false;
        char saved = grid[r][c];
        grid[r][c] = '#';
        bool found = self(self, r + 1, c, i + 1) || self(self, r - 1, c, i + 1) || self(self, r, c + 1, i + 1) || self(self, r, c - 1, i + 1);
        grid[r][c] = saved;
        return found;
    };
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            if (dfs(dfs, r, c, 0)) return true;
        }
    }
    return word.empty();
}

N-Queens

Problem. Place $n$ queens on an $n\times n$ board so that no two attack each other (no shared row, column or diagonal). Count the solutions, or find one.

Backtracking with bitmasks — the standard solution

Place one queen per row; track occupied columns and both diagonal families as bitmasks — this is exactly queens from Backtracking above:

// void queens(int row, int cols, int d1, int d2, int n, int& count) — see Backtracking
// call: int count = 0; queens(0, 0, 0, 0, n, count);

avail & -avail isolates the lowest available column, so the loop visits each candidate once. $n=15$ runs in well under a second; $n=17$ takes a few seconds.

Proof: the bitmask diagonal propagation is correct

Represent the board with row $r$, column $c$. The two diagonal families are $c-r=\text{const}$ ("$\nearrow$", constant along one diagonal direction) and $c+r=\text{const}$ ("$\searrow$"). Track them as bitmasks d1 (the $\searrow$ family, bit $i$ meaning “column $i$ is blocked on this diagonal as seen from the next row”) and d2 (the $\nearrow$ family) — the trick is to store them already shifted so that row-to-row propagation is a plain bit shift.
If a queen occupies column $c$ in row $r$, it attacks column $c+1$ of the $\searrow$ diagonal family in row $r+1$ (moving down-right increases both row and column by 1, so the attacked cell in the next row is one column to the right) and column $c-1$ of the $\nearrow$ family in row $r+1$ (moving down-left decreases the column). So if bit (with the single bit at position $c$) is OR’d into the current row’s diagonal masks and then the $\searrow$ mask is shifted left by 1 (moving every blocked column up by one position, matching "$c\to c+1$") and the $\nearrow$ mask shifted right by 1 (matching "$c\to c-1$"), the result is exactly next row’s blocked-column set from diagonals, carried forward automatically — which is (d1 | bit) << 1 and (d2 | bit) >> 1. Combined with cols (columns blocked directly, unaffected by row, no shift needed), avail = ~(cols|d1|d2) & ((1<<n)-1) is exactly the set of columns safe for row $r+1$, and the recursion visits every root-to-leaf assignment of one queen per row with no two sharing a column or diagonal — by induction, every recursive call’s masks correctly reflect every queen placed so far. $■$

Solution counts

$n$	Solutions	$n$	Solutions
1	1	8	92
2	0	9	352
3	0	10	724
4	2	12	14 200
5	10	15	2 279 184
6	4	20	$3.9\cdot 10^{10}$
7	40	27	$2.3\cdot 10^{17}$ (the largest computed)

No closed form is known, and counting is believed hard. $n=27$ was computed in 2016 with a large distributed effort.

Constructing one solution in $O(n)$

Counting is hard; finding a single solution is easy. Explicit formulas exist for every $n\ge 4$:

• $n$ even, $n\not\equiv 2(\mathrm{mod}6)$: place queens at $(i,2i)$ for $i\le n/2$ and $(i,2i-n-1)$ for the rest.
• Other cases have similar formulas with small adjustments.

So “output any valid placement” is $O(n)$ and needs no search at all — worth knowing, because contest versions usually ask for a solution, not the count.

Symmetry breaking

The board has 8 symmetries (the dihedral group $D_4$). Restricting the first queen to the first half of the first row roughly halves the search, and correcting for the fixed points recovers the exact count.

More aggressive: classify solutions by their symmetry class (asymmetric, 180°-symmetric, 90°-symmetric) and count each with the appropriate multiplier — a Burnside argument.

As exact cover

N-Queens is an exact cover problem with:

• primary columns (must be covered exactly once): each rank, each file;
• secondary columns (at most once): each of the $2(2n-1)$ diagonals.

Dancing Links with optional columns solves it directly, and this is the standard demonstration of secondary columns.

Variants

Variant	Note
Count solutions	no closed form; $n\le 17$ by search
Find any solution	$O(n)$ construction
Solutions up to symmetry	”fundamental” solutions; 12 for $n=8$
Queens on a torus	solvable iff $\gcd (n,6)=1$
$n$ superqueens (queen + knight moves)	much more constrained
Minimum queens to dominate the board	a different (domination) problem
Maximum non-attacking rooks	trivially $n$
Maximum non-attacking knights	$\lceil n^2/2\rceil$ — one colour class
Maximum non-attacking bishops	$2n-2$
Peaceable queens (two armies)	an open problem

Why it is worth knowing

It is the canonical demonstration of three ideas:

1. Bitmask state — three integers encode all the constraints, and the transitions are shifts.
2. Backtracking with $O(1)$ constraint checks — the pruning is free.
3. Counting is harder than constructing — a recurring asymmetry (see also permanent vs determinant, and matchings).

Knight’s Tour

Problem. Move a knight over every square of an $n\times n$ board exactly once. A closed tour returns to the start; an open tour need not.

This is a Hamiltonian path problem on the knight-move graph — NP-hard in general, but easy here because the graph is highly structured.

Warnsdorff’s rule — the key heuristic

Always move to the square with the fewest onward moves.

This is exactly knightsTour from Backtracking Puzzles above (which additionally rotates the tie-break order on failure and retries, a cheap robustness improvement over the bare greedy rule).

It almost never backtracks. Warnsdorff’s rule finds tours on boards up to $100\times 100$ essentially instantly, despite the underlying problem being NP-hard. No proof of correctness is known — it is an empirically reliable heuristic, not a guaranteed algorithm (see the divide-and-conquer construction below for a method that is guaranteed).

The intuition: squares with few remaining exits become unreachable if not visited soon, so visit them first. It is exactly the most-constrained-first heuristic from backtracking.

For robustness, break ties by distance from the centre, and add backtracking as a fallback.

Existence

Board	Open tour	Closed tour
$n\times n$, $n\ge 5$	yes	yes iff $n$ is even
$n\times n$, $n$ odd	yes	no
$3\times 3$	no (the centre is isolated)	no
$4\times 4$	no	no
$5\times 5$	yes	no
$m\times n$, general	Schwenk’s theorem gives the exact conditions

Why no closed tour on odd boards: a knight alternates colours every move. A closed tour has $n^2$ moves, so it needs equally many squares of each colour — impossible when $n^2$ is odd. A clean parity argument.

Schwenk’s theorem. An $m\times n$ board ($m\le n$) has a closed tour unless: $m$ and $n$ are both odd; or $m\in \{1,2,4\}$; or $m=3$ and $n\in \{4,6,8\}$.

Divide and conquer

For large boards, split into quadrants, find a tour in each (recursively or from a base case), and stitch them together by breaking one edge in each and reconnecting. Gives an $O(n^2)$ construction with a guarantee, rather than relying on a heuristic.

Counting tours

The number of closed tours on $8\times 8$ is 26 534 728 821 064 — computed by exhaustive search with heavy symmetry reduction. There is no formula, and counting is far harder than finding.

Variants

Variant	Note
Closed tour	needs even $n$
Tour from a specific square	usually possible on large boards
Tour visiting squares in a given order	much harder
Knight’s distance between two squares	a closed form exists, or BFS
Minimum knight moves on an infinite board	a formula based on $|\Delta x|,|\Delta y|$
Knight moves on a torus / 3D board	different existence conditions
Other pieces (camel, giraffe)	same framework, different move sets

Knight distance on an infinite board is worth knowing: for $(x,y)$ with $x\ge y\ge 0$, the answer is a small case analysis around $\max \left(\lceil x/2\rceil ,\lceil (x+y)/3\rceil \right)$ adjusted for parity, with special cases near the origin. Contest problems often ask exactly this — and a BFS over a bounded region also works.

Why it is worth knowing

It is the standard illustration that a good ordering heuristic can beat exponential search. Warnsdorff’s rule has no proof of correctness, yet it works on every board anyone has tested — a useful reminder that “NP-hard” describes the worst case, not the instances you meet.

Pruning and branch and bound

Exponential searches become practical when most branches are cut early. Every pruning rule must be safe: it may only discard branches that cannot beat (or reach) the best answer.

Rule	Safe because
bound: optimistic estimate $\le$ best so far	the branch cannot improve the answer
feasibility: remaining resources cannot satisfy the constraints	no completion exists
symmetry breaking: force an order on interchangeable choices	every solution has a representative in the allowed order
dominance: state A is at least as good as B in every respect	any completion of B also completes A at least as well
memoization of failed states	the same subproblem fails again
good ordering: most constrained first, best value first	finds strong solutions early, so the bound prunes more

Branch and bound for knapsack

Sort by value density; the fractional relaxation of the remaining items is an upper bound.

long long knapsackBB(vector<pair<int, int>> items, int cap) {   // {weight, value}; branch and bound with fractional bound
    sort(all(items), [](auto a, auto b) { return (long long)a.second * b.first > (long long)b.second * a.first; });
    int n = sz(items); long long best = 0;
    auto bound = [&](int i, int w, long long v) {            // fractional relaxation of the rest
        double b = v; int room = cap - w;
        for (; i < n && items[i].first <= room; i++) room -= items[i].first, b += items[i].second;
        if (i < n) b += (double)items[i].second * room / items[i].first;
        return b;
    };
    auto rec = [&](auto self, int i, int w, long long v) -> void {
        best = max(best, v);
        if (i == n || bound(i, w, v) <= best) return;
        if (w + items[i].first <= cap) self(self, i + 1, w + items[i].first, v + items[i].second);
        self(self, i + 1, w, v);
    };
    rec(rec, 0, 0, 0);
    return best;
}

Proof: the fractional bound never prunes an optimal branch

For fractional knapsack, taking items in decreasing order of value per weight (and a fraction of the first item that does not fit) is optimal, by an exchange argument: moving weight from a lower-density item to a higher-density one never decreases the value. Every integral completion of the current partial solution is a feasible fractional solution of the remaining instance, so its value is at most the bound. Pruning when the bound is $\le$ the best found therefore never discards a strictly better solution. Tested against the $O(n\cdot \text{cap})$ DP.

Related: Backtracking, Informed Search, Maximum Clique.