Backtracking

Backtracking = try, explore, undo.

Example: permutations

def perm(nums):
    res = []

    def dfs(path, used):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            dfs(path, used)
            path.pop()
            used[i] = False

    dfs([], [False]*len(nums))
    return res

print(perm([1,2,3]))

Graph

flowchart TD
  A[Start] --> B[Choose 1]
  B --> C[Choose 2]
  C --> D[Choose 3]

Remember

• explore all paths
• undo after each try
• used in puzzles and search