Choices, constraints, and undo

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

A search state contains a partial candidate plus remaining choices. Choose one option, recurse only if constraints allow it, then undo before trying the next sibling.

Work through an example

Subset generation includes or excludes each element. After exploring inclusion of 1, path.pop removes it so the next branch starts from the correct parent state.

Time and space complexity

O(search states plus output copying); depth O(n), excluding outputs.

Why it works

On return, the caller's path and resource state are exactly as they were before the choice.

Common mistakes

Missing undo contaminates siblings.
Saving path instead of path.copy aliases all outputs.

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