— Algorithms — 2 min read
Backtracking is often used when we need to generate all combinations, permutations of a given set (array, graph, etc.), but we usually need to satisfy some constraints or a condition.
- We need to traverse the input in the DFS function
- 1D input (string, nums array) - pass an index
- 2D input (matrix) - pass row, col
- Check for in bounds and seen coordinates
- For the recursive function, we need to define a base-case
1if i >= len(nums):2 return3if not in_bounds(row, col):4 return5if rem < 0:6 return
- Then we iterate over the options we have
- This could be numbers 1-9, characters in a dictionary, positions in matrix
- in the 2D grid we can move by using the direction array (up, down, left, right)
1directions = [[0,1], [1,0], [0,-1], [-1,0]]2def dfs(row, col, state):3 # .... logic4 for dx, dy in directions:5 r, c = row + dx, col + dy6 # ... logic
- We would modify the state on each iteration (via DFS call)
- We need to revert to the previous state after each recursive call
Following this approach, we can solve many problems that require backtracking.
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Link to the problem
We define a recursive function
dfs that takes an index
i as an argument. This is how we'd traverse the input array.
Then we define a base-case:
if i == n, this means we have a valid permutation -> we can add it to the result and return from the function.
Then we iterate over the options we have: we swap the current element with all the elements after it and call the recursive function with
After the recursive call, we swap the elements back to the original state to backtrack.
See the solution below:
1def permute(self, nums: List[int]) -> List[List[int]]:2 res = 3 n = len(nums)4 def dfs(i):5 if i == n:6 res.append(nums[:])7 return89 for j in range(i, n):10 nums[i], nums[j] = nums[j], nums[i]11 dfs(i+1)12 nums[i], nums[j] = nums[j], nums[i]13 dfs(0)14 return res
Some other problems that can be solved using backtracking: