Skip to content
BS | @bskokdev


Algorithms2 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.

My approach

  • 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 return
3if not in_bounds(row, col):
4 return
5if 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 # .... logic
4 for dx, dy in directions:
5 r, c = row + dx, col + dy
6 # ... 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 i+1. 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 return
9 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: