Pruning

What is backtracking?

Backtracking systematically tries choices to build a solution. Make one choice, explore what follows, then undo that choice before trying another. A constraint is a rule a valid solution must satisfy. Rejecting a partial solution as soon as it breaks a constraint avoids exploring choices that cannot work.

Example: To form subsets of [1, 2], choose whether to include 1, then whether to include 2. The four results are [], [1], [2], and [1, 2]. Undo each choice before taking a different branch.

Helpful before this chapter

If these ideas are new, begin with:

Recursion

Understand the idea

Pruning rejects partial states that cannot lead to a valid answer. The rejection must be logically necessary. A bound can also stop branches that cannot improve the best known objective.

Work through an example

For size-three combinations, stop when remaining elements are fewer than still-needed slots. For positive-only sum combinations, stop when the sum exceeds the target.

Time and space complexity

Pruning reduces visited states but does not automatically remove exponential worst cases.

Why it works

No pruned branch can contain a valid or better solution under the stated assumptions.

Common mistakes

Sum-based pruning fails with negative future values.
A heuristic alone is not proof a branch is impossible.

Chapter lab · Python implementation

Backtracking explores choices while restoring the partial state after each branch. Our subset lab uses choose/undo operations; duplicate-aware permutations demonstrate per-level duplicate avoidance. Outputs must be copied because the working path will change. Exponential output cannot be made linear by a clever traversal.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def subsets(values):
    output,path=[],[]
    def visit(i):
        if i==len(values):
            output.append(path.copy()); return
        visit(i+1)
        path.append(values[i])
        visit(i+1)
        path.pop()
    visit(0)
    return output

def unique_permutations(values):
    values=sorted(values)
    used=[False]*len(values)
    output,path=[],[]
    def visit():
        if len(path)==len(values):
            output.append(path.copy()); return
        for i,x in enumerate(values):
            if used[i]: continue
            if i and x==values[i-1] and not used[i-1]: continue
            used[i]=True; path.append(x)
            visit()
            path.pop(); used[i]=False
    visit()
    return output

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert sorted(subsets([1,2]))==[[],[1],[1,2],[2]]
assert subsets([])==[[]]
assert unique_permutations([1,1,2])==[[1,1,2],[1,2,1],[2,1,1]]
assert unique_permutations([])==[[]]

CHECK YOUR UNDERSTANDING