Subsets and combinations

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

Subsets choose any items; combinations choose a fixed number and ignore order. Advancing a start index prevents reuse and prevents generating the same unordered selection in different orders. A size-k combination can stop as soon as path length reaches k, copying that path. If fewer than k-len(path) candidates remain, return immediately: no descendant can fill the missing positions.

Work through an example

From [1,2,3], size-two combinations are [1,2],[1,3],[2,3]. Choosing 2 after 1 then continuing only beyond 2 avoids [2,1].

Time and space complexity

Subsets require Θ(n2^n) output copying in general; combinations Θ(k×C(n,k)) output.

Why it works

Chosen indices strictly increase, so every combination has one construction path.

Common mistakes

Whether candidates can be reused changes recursion's next start.
Empty selection is a valid size-zero combination.

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