- we abandon a "path" once we know it can't branch into a solution
- used when problem wants you to find solution by generating everything / checking all logical possibilities
- below code example is to find all possible string sequences of length $n$ using letters $a-z$ that only have vowels, which reduces from $26^n$ possibilities to $5^n$
- is just [[DFS]] on state space of possible generations
- almost always implemented with [[Recursion]]
## Backtracking Template
```
// let curr represent the thing you are building
// it could be an array or a combination of variables
function backtrack(curr) {
if (base case) {
Increment or add to answer
return
}
for (iterate over input) {
Modify curr
backtrack(curr)
Undo whatever modification was done to curr
}
}
```
## Classic Backtracking/Generation Templates
#### Permutation
```
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(curr):
if len(curr) == len(nums):
ans.append(curr[:])
return
for num in nums:
if num not in curr:
curr.append(num)
backtrack(curr)
curr.pop()
ans = []
backtrack([])
return ans
```
#### Subsets
- idea is each subset has a unique starting point
- you always have a choice: you can pick this number, or skip it
```
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def backtrack(curr, i):
if i > len(nums):
return
ans.append(curr[:])
for j in range(i, len(nums)):
curr.append(nums[j])
backtrack(curr, j + 1)
curr.pop()
ans = []
backtrack([], 0)
return ans
```
#### Combinations
- combos & subsets are same thing
- but here you have a specific required length
```
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(curr, i):
if len(curr) == k:
ans.append(curr[:])
return
for num in range(i, n + 1):
curr.append(num)
backtrack(curr, num + 1)
curr.pop()
ans = []
backtrack([], 1)
return ans
```
- below is a good basic [[DFS]] path problem that introduces the backtracking tree state space relationship well
https://leetcode.com/problems/all-paths-from-source-to-target/