Backtracking

Choose, explore, un-choose

At each step: make a choice, recurse, then undo the choice before trying the next. Prune branches that already violate a constraint. It's DFS over the tree of partial solutions.

All permutations

path is the current partial arrangement; add, recurse, pop.

def permutations(nums):
    res, path, used = [], [], [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i, n in enumerate(nums):
            if used[i]:
                continue
            used[i] = True; path.append(n)
            bt()
            used[i] = False; path.pop()   # un-choose
    bt()
    return res

Classic problems

Subsets, combinations, permutations, N-Queens, Sudoku, word search, generating valid parentheses. Cost is often exponential — good pruning is the whole game.