Permutations

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

Permutations arrange all items, so order matters. Track used positions rather than a monotonically increasing start. Each depth fills one output slot with one unused input position.

Work through an example

[1,2,3] has six permutations. Choosing 2 first still permits 1 later; a start-index-only loop would incorrectly omit that ordering.

Time and space complexity

Θ(n×n!) output time for distinct values, O(n) working state/depth.

Why it works

No input position is used twice; path length equals the number of used positions.

Common mistakes

Value-based used sets fail when duplicate positions are legitimate.
Reset used flags during undo.

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