Backtracking: Try, and Undo

Exploring every possibility, neatly

Backtracking builds an answer one choice at a time. After exploring everything that follows a choice, it undoes that choice and tries the next one.

Think of it like this: Trying a combination lock digit by digit: set the first digit, try every option for the rest; then change the first digit and do it again.

The pattern is always: choose → explore → un-choose.

All subsets

def subsets(items):
    result = []
    current = []

    def explore(i):
        if i == len(items):
            result.append(current[:])      # save a copy
            return
        current.append(items[i])           # choose: take items[i]
        explore(i + 1)
        current.pop()                      # un-choose
        explore(i + 1)                     # skip items[i]

    explore(0)
    return result

print(subsets(["a", "b", "c"]))

Output

[['a', 'b', 'c'], ['a', 'b'], ['a', 'c'], ['a'], ['b', 'c'], ['b'], ['c'], []]

Each item is either in or out, so there are 2ⁿ subsets: O(2ⁿ).

All orderings (permutations)

def permutations(items):
    result = []
    current = []
    used = [False] * len(items)

    def explore():
        if len(current) == len(items):
            result.append("".join(current))
            return
        for i in range(len(items)):
            if not used[i]:
                used[i] = True
                current.append(items[i])
                explore()
                current.pop()
                used[i] = False

    explore()
    return result

print(permutations("abc"))

Output

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

n choices for the first place, n − 1 for the second, ...: n! orderings, so O(n!).