## What is backtracking?

Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.

Essentially, backtracking is dfs on a tree of possible solutions.

## Backtracking template

For a general backtracking, we need to write a base case for the end condition, a loop for the choices, and a recursive call.

```
def backtrack(path, choices):
if end_condition(path):
res.append(path)
return
for choice in choices:
if is_valid(path, choice):
path.add(choice)
backtrack(path, choices)
path.remove(choice)
```

You can remove the `path.add(choice)`

and `path.remove(choice)`

if you just add the choice to the path in the recursive call.

```
backtrack(path + [choice], choices)
```

There are many variations of backtracking, such as the subset sum problem, n-queens problem, and sudoku.

## Variations

We can moidy the template to fit different problems.

### Permutations

For permutations, we need to add a visited set to keep track of the visited elements.

```
def backtrack(path, choices, visited):
if end_condition(path):
res.append(path)
return
for choice in choices:
if is_valid(path, choice):
path.add(choice)
visited.add(choice)
backtrack(path, choices, visited)
path.remove(choice)
visited.remove(choice)
```

### Combinations

For combinations, we need to add a start index to avoid duplicates.

```
def backtrack(path, choices, start):
if end_condition(path):
res.append(path)
return
for i in range(start, len(choices)):
if is_valid(path, choices[i]):
path.add(choices[i])
backtrack(path, choices, i + 1)
path.remove(choices[i])
```

### Duplicated input

For duplicated input, we need to sort the input and skip the duplicated elements.

```
def backtrack(path, choices, start):
if end_condition(path):
res.append(path)
return
for i in range(start, len(choices)):
if i > start and choices[i] == choices[i - 1]:
continue
if is_valid(path, choices[i]):
path.add(choices[i])
backtrack(path, choices, i + 1)
path.remove(choices[i])
```

### Multiple solutions on one path(Subsets)

For subsets, we need to add the result to the result list, and we do not need to check the end condition.

```
def backtrack(path, choices, start):
result.add(path)
for i in range(start, len(choices)):
if is_valid(path, choices[i]):
path.add(choices[i])
backtrack(path, choices, i + 1, result)
path.remove(choices[i])
```