Examples / Recursion & backtracking▶Run in PyTrace
Recursion and Backtracking Visualization in Python
Backtracking explores choices recursively: make a choice, recurse, then undo the choice and try the next one. It is how you generate subsets, permutations and combinations, and how you solve problems like N-Queens or Sudoku.
Recursion is hard to trace in your head because each call has its own variables. PyTrace shows the call stack: every backtrack(start) frame with its own start and i, while the shared path grows with append and shrinks with pop.
ComplexityO(n · 2ⁿ) time: there are 2ⁿ subsets and copying each costs up to n.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
result = []
path = []
def backtrack(start):
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return resultInputs
nums[1,2,3]
expected[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]
What to watch
- The call stack growing with each
backtrack(i + 1)and unwinding on return pathbeing extended and undone: the essence of backtrackingresultcollecting a copy ofpathat every node of the recursion tree