Duplicate avoidance

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

Duplicate avoidance should prevent equivalent branches at the same decision level. Sorting makes equal candidates adjacent. For permutations, use the previous equal item before a later equal unused item.

Work through an example

[1,1,2] yields only [1,1,2],[1,2,1],[2,1,1]. Equal positions can both appear in a path, but exchanging indistinguishable copies creates no new answer.

Time and space complexity

Work follows unique search states, plus sorting O(n log n); worst remains factorial.

Why it works

At each depth, equivalent unused values are explored once in a consistent order.

Common mistakes

Skipping all equal values globally loses valid repeated elements.
The used[i-1] condition distinguishes depth from path duplication.

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