# Backtracking

## Overview

Backtracking is a general algorithmic technique that involves exploring all possible solutions to a problem by incrementally building a solution and then undoing (or "backtracking" on) the choices that lead to dead ends. It is a form of depth-first search and is particularly useful for solving problems that involve searching through a large number of possibilities, such as finding all possible solutions to a problem or finding the one solution that satisfies a set of constraints.

The steps for using backtracking to solve a problem are as follows:

- Understand the problem and its requirements by reading the problem statement and examples.
- Develop a recursive algorithm that incrementally builds a solution and backtracks when a dead end is reached.
- Define a base case for the recursion that indicates when a complete solution has been found, and a terminating condition that indicates when to stop the recursion.
- Test the solution on the provided test cases to check if it works correctly and returns the expected output.

Backtracking can be used for various of problems such as:

- Generating all possible combinations of a set of items.
- Finding all possible solutions to a problem
- Finding a specific solution that satisfies a set of constraints.
- Solving puzzles or other combinatorial problems
- And many more

Backtracking can be very inefficient, especially when the number of possible solutions or the size of the input is large. Therefore, it is important to carefully analyze the problem and develop an efficient backtracking algorithm.

## Example: 0046 - Permutations (Medium)

If we have an array $nums$ of distinct integers, what are all the possible permutations? If the input is $[1,2,3]$, then the permutations would be $[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]$. In C++, it is easy to solve this problem by using the built-in STL **next_permutation**. However, we can also solve it using backtracking.

The general steps are as follows.

1. Sort the input array if necessary. However, in this example, sorting is not necessary.

`sort(nums.begin(), nums.end());`

2. Define `ans`

and `tmp`

where `ans`

is the array storing all final permutations and `tmp`

is used to store possible permutations at some point.

`vector<vector<int>> ans;`

vector<int> tmp;

3. Call `backtrack()`

function in main

`backtrack(nums, ans, tmp);`

4. Let's add logic in `backtrack()`

function. First we need to define the exit criteria. When should we push `tmp`

to `ans`

? If `tmp`

already got enough candidates, then we can push `tmp`

to `ans`

.

`if ((int) tmp.size() == (int) nums.size()) {`

ans.push_back(tmp);

return;

}

5. Iterate each number, check If the candidate has been used or not, skip it if it is already in `tmp`

. Otherwise, push it to `tmp`

and call `backtrack()`

again. After that, remove the previous candidate from `tmp`

and move to the next candidate.

`for (auto x : nums) {`

if (find(tmp.begin(), tmp.end(), x) != tmp.end()) continue;

tmp.push_back(x);

backtrack(nums, ans, tmp);

tmp.pop_back();

}

### Suggested Problems

Problem Name | Difficulty | Solution Link |
---|---|---|

0039 - Combination Sum | Medium | View Solutions |

0040 - Combination Sum II | Medium | View Solutions |

0046 - Permutations | Medium | View Solutions |

0078 - Subsets | Medium | View Solutions |