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.

Reach for when

• You need every solution.
• You build an answer step by step do vs dont.

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