Description

Backtracking is a Depth First Search on the tree of partial solutions. It works well when we have a continue vs dont continue flow. Make a choice, explore where it leads, then UNDO the choice and try the next one — the undo (jumping back to the previous state) is what makes it backtracking. Pruning branches that can't lead to a valid solution ("dont continue") as early as possible is where all the speed comes from.

Use it to enumerate all configurations: permutations, combinations, subsets, N-Queens, Sudoku, word search.

Runtime

Exponential — the solution tree is the cost: O(2^n) for subsets, O(n!) for permutations. Pruning shrinks the tree but not the worst case.

Visualization

Pseudocode

answers = []

def backtrack(current_state):
	if solution(current_state):
		answers.append(current_state)
	else:
		for option in options:
			if we want to take option:      # prune here
				take option                 # choose
				backtrack(new_state)        # explore
				undo option                 # un-choose

Code

def permutations(nums):
    res = []
    path = []

    def backtrack():
        if len(path) == len(nums):     # solution
            res.append(path[:])        # record a copy
            return

        for n in nums:                 # each option
            if n in path:              # prune: already used
                continue
            path.append(n)             # choose
            backtrack()                # explore
            path.pop()                 # un-choose

    backtrack()
    return res