# Backtracking

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

## 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 return8
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: