## 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.
-Wikipedia

Let’s understand this statement in a more friendly way. All backtracking problems have a solution space. If you are looking for a particular solution, it lies within the solution space. The particular solution matches the constraints put in the problem domain.
Solution space is usually a tree-shaped. At every node, you have multiple choices and you do not have any way to find which choice will lead to the solution. So, we try every choice as far as the choice is safe according to the problem domain. If no solution is found after trying all the choices, we backtrack and take the next choice at the parent of the current node.

If we explore all the paths of this solution space, it leads to exhaustive search.

However, in backtracking, we can take a decision, whether continuing the path will ever lead to a solution? If not, we will abandon the path altogether and go to the parent node and take a different choice. This is called pruning of solution space.
Moving back to the parent node in the solution space is implicitly done using recursion, that’s why exhaustive search and backtracking problems have a recursive implementation.

Backtracking is an important tool for solving constraint satisfaction problems such as 8 queens problem, Sudoku, and many other puzzles.

## General problem structure of backtracking problem

There are 4 steps to solve a backtracking problem.

1. Check if the current state is the final state if yes, then do the bookkeeping and return.
2. If not, enumerate all the possible choices/options you have to go from here.
3. Loop through all the choices one by one
1. If the choice is safe, make the choice.
2. Try to solve the problem with the choice made above.
3. If the problem is solved, return (This is applicable only if we are interested only 1 solution)
4. Unmake the choice we made in 3.1
4. If we are looking for one solution and did not return from 3.3, return false, else just return.

Let’s see some problems and make sure that we understood the backtracking algorithm steps..

### Example problem 1: 8 queen problem

```class Solution {
public List<List<String>> solveNQueens(int n) {

char[][] board = new char[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
board[i][j] = '.';
}
}

List<List<String>> res = new ArrayList<>();
solve(board, 0, res, n);

return res;
}

void solve(char [][] board, int col, List<List<String>> res, int n){

/* Step 1: Check if the current state is our final step,
do the bookkeeping
In this case, we check if we considered all the columns,
we put the board state as a solution.
*/
if (col >= board.length) {
}

/* Step 2: Next, enumerate all the choice. We have to try
each row for the current queen */
for (int rowToTry = 0; rowToTry < n; rowToTry++) {
//3.1 Check if the current choice for the queen is safe
if (isSafe(board, rowToTry, col)) {
//3.2 Make the choice
board[rowToTry][col] = 'Q';
//3.3 if the choice we made actually solves the problem.
solve(board, col + 1, res, n);
//3.4 unmaking the choice
board[rowToTry][col] = '.';
}
}
//Step 4.
return;
}

//Auxiliary functions are specific to the domain of the problem.
List<String> formatOutput(char[][] board, int n){

List<String> l = new ArrayList<>();

for(int i=0; i<n; i++){
}
return l;
}

boolean isSafe(char[][] board, int row, int col){

for(int i = 0; i < board.length; i++) {
for(int j = 0; j < col; j++) {
if(board[i][j] == 'Q'
&& (row + j == col + i
|| row + col == i + j
|| row == i))
return false;
}
}
return true;
}
}
```

### Example problem 2: Find permutation problem

```class Solution {
public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> res = new ArrayList<>();
findPermutations(nums, new ArrayList<Integer>(), res);
return res;
}

private void findPermutations(int [] nums, List<Integer> current,
List<List<Integer>> res){

/* Step 1. Check if the current state is the solution
In this problem, if the length of the current list is equal
to the size of the array, we have all the integers in
the current permutation, so adds it to the result.
*/
if(current.size() == nums.length){
}

/* Step 2: What all choices we have, in permutations, all the
integers are possible choice, so we will go through all of them
*/
for(int i=0; i<nums.length; i++){

/* 3.1 Check if this number is safe for the solution,
In permutation, each number can be present only once.
So, skipp the number if it is already in the current
permutation.
*/
if(current.contains(nums[i])) continue;

//3.2 Make the choice, add the num in current permutation

//3.3 Solve the problem with the above choice made.
findPermutations(nums, current, res);

//3.4 Unmake the choice
current.remove(current.size()-1);
}

//4. Return;
return;
}
}
```

### Example problem 3: Find subsets

```class Solution {

public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();

subsetsUtil(nums, 0, new ArrayList<Integer>(), result);
return result;
}

private void subsetsUtil(int[] nums, int index, List<Integer> current,
List<List<Integer>> res){

/* Step 1. Check if the current state is the solution
Every new element make a new set, so will add to the
subset list.
*/

/* Step 2: A set can contain an element only once,
and order does not matter. So we will go through
all the elements which are remaining.
*/
for(int i=index; i<nums.length; i++){
//3.1. Every element is safe for a subset, so no check

//3.2 Make the choice, add each

//3.3 Solve the remaining problem.
subsetsUtil(nums, i+1, current, res);

//3.4 Unmake the choice
current.remove(current.size()-1);
}

//4. Return
return;
}
}
```

### Example problem 4: Combination sum

```class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<List<Integer>> ();
combinationSumUtil(candidates, target,
0, new ArrayList<Integer> (), result);

return result;
}

public void combinationSumUtil(int[] candidates, int target,
int index,
List<Integer> current,
List<List<Integer>> res ){

/* Step 1: If the target has gone below zero,
nothing can be done.
However, if the target is zero, then we found a
the combination that adds up to the target,
so we put it into the list.
*/
if(target < 0){
return;
}
if(target == 0){
return;
}

/* Step 2. Once we take the number, remaining numbers
are still available as choices, including the current number.
*/
for(int i=index; i<candidates.length; i++){
//3.1 : Is the choice safe
if(target - candidates[i] >=0){

//3.2 : Make the choice

//3.3 Try to solve with the problem with above choice
combinationSumUtil(candidates,
target-candidates[i], i,
current, res);

//3.4 Unmake the choice
current.remove(current.size()-1);
}
}

//Step 4: return
return;
}
}
```

Please share if there is something wrong or missing. If you are preparing for an interview and need help with preparations, please book a free session with us.

Posted on Categories Algorithms, Backtracking1 Comment on Backtracking algorithms

# Combination sum problem

Given an array of integers (`candidates`) (without duplicates) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sums to `target`.

Also, the same candidate can occur in the combination multiple times.

For example, Input: candidates = [4,3,5,9], target = 9, a solution set is:[ , [3,3,3], [4,5]]

How can do we go about it? What happens if I take the coin 4 in the current example? Then all need to find in the `candidates` array if there is a combination adds up to 9-4 = 5. It seems like a recursion. For recursion, we need a termination condition. In this case, if I have on candidates to add and `target` is greater than zero, then whatever combination I have till now has no value, so I terminate the recursion in this case.

Second what if I have already found a combination that adds up to `target`? Then I will put that combination in the list of combinations and return.

What happens in recursive implementation? Well, we go through each coin, add that to the current combination and see if leads to the target? If it does, it will be added to the result list along with the list of other candidates. If not, we just remove the current coin (backtrack) from the current combination and try the next coin.

This approach is called the exhaustive search and backtracking paradigm of problem-solving where you search the entire input set to see to find the answer. However, in this case, we can prune the search path as soon as we know that the current set of candidates add up more than the target.

## Combination sum : implementation

```class Solution {
public List<List<Integer>> combinationSum(int[] candidates,
int target) {
/* The result list contains all the combination
*/
List<List<Integer>> result = new ArrayList<List<Integer>> ();

combinationSumUtil(candidates,
target,
result,
new ArrayList<Integer>(),
0
);

return result;

}

public void combinationSumUtil(int[] candidates,
int target,
List<List<Integer>> result,
List<Integer> current,
int index){

/*
First termination condition: if there are no coins left
and required target is more than zero.
*/
if(target > 0 && index == candidates.length){
return;
}

/*
Second termination condition: if target is zero,
we can add the current combination to the result
*/
if(target == 0 && index < candidates.length){
return;
}

/*
Start from the current index, and go through
all the coins.
*/
for(int i=index; i<candidates.length; i++){
/*
This is where we prune the branches
of our exhaustive search
*/
if(target - candidates[i] >=0){
combinationSumUtil(candidates,
target-candidates[i],
result, current, i);

/* Remove the candidate from the list and
check other combinations.
*/
if(current.size() > 0)
current.remove(current.size()-1);
}
}

}
}
```

The time complexity is C(n,1) + C(n,2) + … + C(n,n) = 2^n – C(n,0) = `O(2n)`.

The beauty of this solution is that it works with negative candidates as well, where the Dynamic programming solution for it may not work.

# Backtracking : Eight Queens problem

Given N x N chessboard, find a way to place N queens such that none of the queen can attack other. A queen can move along the column, row and diagonal of the chess board.

This is typical example of backtracking algorithm. What we need to do is that start with the first queen at the bottom left position and check all other queens can be place satisfying the constraints of the game. If at nay point we can not go forward, we try to replace the previous queen on next safe location and try again. If we are stuck at dead end, then we might need to replace more than one queen from their position so that we can move forward.
Let’s take this example, you have a 4 x 4 chessboard and you need to place four queens on it.
We place the queen at the left most bottom corner. Once we place queen there, our available options are for placing queen 2 are shown.

Looking at the figure below we can infer that there is no way possible to place Q3 and Q4 both with current configuration. Hence we back track and select another available position for Q2

Again we can’t place Q3 and Q4, and we try all other available positions for Q2, but none of those work .(exercise). Hence we change the position of the Q1.
After changing the position of Q1, we can reach the solution as shown in figure below, with couple of more backtracks of course.

Next step to figure out that if the queens is safe at a particular position. We need to check the column, row and diagonal, to make sure no other queen is placed in those places.  ## 8 Queen solution implementation

```#include &lt;stdio.h&gt;
#define N 8

int isColumnSafe(int chessBoard[N][N], int col){

for(int i=0; i&lt;N; i++){
if(chessBoard[i][col]) return 0;
}
return 1;
}

int isRowSafe(int chessBoard[N][N], int row){

for(int i=0; i&lt;N; i++){
if(chessBoard[row][i]) return 0;
}
return 1;
}

int isDiagonalSafe(int chessBoard[N][N], int row, int col){

int j;

/* Check the left upper diagonal */

for(int i=row, j = col; i&gt;=0 &amp;&amp; j&gt;=0; i--, j--){
if(chessBoard[i][j]) return 0;
}

/*check left lower diagonal */
for(int i=row, j = col; i&lt;N &amp;&amp; j&gt;=0; i++, j--){
if(chessBoard[i][j]) return 0;
}

return 1;
}

int isSafe(int chessBoard[N][N], int row, int col){

int columnSafe = isColumnSafe(chessBoard, col);
int rowSafe = isRowSafe(chessBoard, row);
int diagonalSafe  = isDiagonalSafe(chessBoard, row, col);

return columnSafe &amp;&amp; rowSafe &amp;&amp; diagonalSafe;
}

void placeQueen(int chessBoard[N][N], int i, int j){
chessBoard[i][j] =1;
}
void removeQueen(int chessBoard[N][N], int i, int j){
chessBoard[i][j] =0;
}

int solveQueens(int chessBoard[N][N], int col){

if(col &gt;= N) return 1;

for(int i=0; i&lt;N; i++){
if(isSafe(chessBoard, i, col)){
placeQueen(chessBoard, i, col);
if(solveQueens(chessBoard,col+1)) return 1;
removeQueen(chessBoard,i,col);
}
}

return 0;
}

int main(void) {
int chessBoard;
solveQueens(chessBoard, 0);

return 0;
}

```

Complexity of backtracking algorithm for 8 queens problem will be O(N*N).>