Backtracking

25.07.2023 — Algorithms — 2 min read

Overview

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.

Example

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
8
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: