Backtracking is a systematic way to explore all possible solutions to a problem by building candidates incrementally and abandoning them ("backtracking") when they cannot lead to a valid solution.
Imagine you're in a maze with multiple paths. You choose one direction, walk as far as you can, and if you hit a dead end, you return to your last decision point and try a different direction. This is exactly how backtracking works in algorithms.
The key insight is that backtracking combines recursion with state management. As you explore deeper (recursion), you build up your current solution. When you need to try a different branch, you undo your last choice (backtrack) and try the next option.
For grid path problems, backtracking is perfect because:
The typical backtracking pattern involves three steps:
This approach guarantees you'll find all possible solutions because it systematically explores every valid combination. The "undo" step is crucial—it ensures that when you try the next option, you're starting from the correct state.
1def find_permutations(nums):
2 result = []
3 current_perm = []
4
5 def backtrack():
6 # Base case: found a complete permutation
7 if len(current_perm) == len(nums):
8 result.append(current_perm.copy()) # Save a copy
9 return
10
11 # Try each unused number
12 for num in nums:
13 if num not in current_perm: # Check if available
14 current_perm.append(num) # Make choice
15 backtrack() # Explore deeper
16 current_perm.pop() # Undo choice (backtrack)
17
18 backtrack()
19 return result