Back to Course

0% Complete
0/0 Steps

Lesson 46 of 48
In Progress

# Backtracking in C++

##### Yasin Cakal

Welcome to this guide on backtracking in C++. Backtracking is an important algorithm used in computer science and is critical to understand for anyone studying data structures and algorithms with C++. This guide will provide an in-depth look at backtracking, including the definition, examples, and how to implement it in C++. By the end of this article, you should have a firm understanding of backtracking in C++, and be able to apply backtracking to solve your own problems.

## What is Backtracking?

Backtracking is a type of algorithm used to solve a problem by exploring all possible solutions. It works by incrementally building a solution and then backtracking to the previous step if the solution does not work. The backtracking algorithm is an effective way to solve complex problems which may otherwise be difficult or impossible to solve.

Backtracking can be used for a wide range of applications, such as solving puzzles or maze problems, or finding the most optimal solution for a problem. It is often used in combination with other algorithms, such as dynamic programming or branch and bound, to further optimize the solution.

Backtracking can also be used to solve problems with multiple solutions. This is because the algorithm can generate all possible solutions and then select the best one.

## How Does Backtracking Work?

Backtracking algorithms work by incrementally building a solution, and then backtracking to the previous step if the solution does not work. This process is repeated until a valid solution is found.

The algorithm starts by setting a variable to the initial state. It then begins to explore all possible solutions, starting with the initial state. If the solution is valid, the algorithm will continue to the next step, otherwise it will backtrack to the previous state and try a different solution. This process is repeated until a valid solution is found, or all possible solutions have been explored.

The backtracking algorithm is an efficient way to solve a problem with multiple solutions, as it is able to generate all possible solutions and then select the best one.

## Example of Backtracking

The following example will demonstrate how the backtracking algorithm works.

The problem we will solve is to find the sum of all possible combinations of numbers from a given set of numbers.

For example, given the set {1, 2, 3}, the algorithm should return the sum of all possible combinations:

• 1 + 2 + 3 = 6
• 1 + 3 + 2 = 6
• 2 + 1 + 3 = 6
• 2 + 3 + 1 = 6
• 3 + 1 + 2 = 6
• 3 + 2 + 1 = 6

The solution to this problem can be solved using the backtracking algorithm.

We start by setting a variable to the initial state. In this case, the initial state is an empty set. We then begin to explore all possible solutions, starting with the empty set.

If the empty set is valid, we add the first number to the set. In this case, the first number is 1. We then check to see if the set is valid. If it is valid, we add the second number to the set. In this case, the second number is 2. We then check to see if the set is valid. If it is valid, we add the third number to the set. In this case, the third number is 3. We then check to see if the set is valid.

If the set is valid, we have found a valid solution and can return the sum of the set (1 + 2 + 3 = 6). If the set is not valid, we backtrack to the previous state (the set with two numbers) and try a different solution. This process is repeated until a valid solution is found, or all possible solutions have been explored.

## Implementing Backtracking in C++

Now that we understand how backtracking works, let’s take a look at how to implement it in C++.

The first step is to create a function that takes in the set of numbers and returns the sum of all possible combinations. This function will be the entry point for our backtracking algorithm.

// Function to find the sum of all possible combinations
int sumOfCombinations(vector<int>& nums)
{
// Initialize sum to 0
int sum = 0;

// Call the backtracking function
backtrack(nums, 0, sum);

// Return the sum
return sum;
} 

Next, we will create the backtracking function. This function will take in the set of numbers, the current index, and the sum.

// Backtracking function
void backtrack(vector<int>& nums, int index, int& sum)
{
// If the index is equal to the size of the set,
// we have reached the end of the set and can
// return the sum
if (index == nums.size())
{
sum += accumulate(nums.begin(), nums.end(), 0);
return;
}

// Loop through the set and add each number
// to the sum
for (int i = index; i < nums.size(); i++)
{
// Add the number to the sum
sum += nums[i];

// Call the backtracking function
backtrack(nums, i + 1, sum);

// Subtract the number from the sum
sum -= nums[i];
}
} 

The backtracking function works by looping through the set of numbers and adding each number to the sum. It then calls the backtracking function with the next index and the updated sum. If the index is equal to the size of the set, we have reached the end of the set and can return the sum.

## Conclusion

In this article, we discussed backtracking in C++, including the definition, how it works, and how to implement it in C++. We also provided an example of backtracking and discussed the advantages of using the algorithm. Backtracking is a powerful algorithm for solving complex problems and is often used in combination with other algorithms to further optimize the solution.

## Exercises

#### Create a function that takes in a string and returns all possible permutations of the string. (Hint: Use backtracking)

// Function to return all possible permutations of a string
vector<string> permute(string s)
{
// Vector to store the permutations
vector<string> perms;

// Call the backtracking function
backtrack(s, 0, perms);

// Return the vector
return perms;
}

// Backtracking function
void backtrack(string s, int index, vector<string>& perms)
{
// If the index is equal to the size of the string,
// we have reached the end of the string and can add
// the string to the vector
if (index == s.size())
{
perms.push_back(s);
return;
}

// Loop through the string and swap each character
// with the character at the current index
for (int i = index; i < s.size(); i++)
{
// Swap the characters
swap(s[index], s[i]);

// Call the backtracking function
backtrack(s, index + 1, perms);

// Swap the characters back
swap(s[index], s[i]);
}
} 

#### Create a function that takes in a 2D array and returns all possible paths from the top-left corner to the bottom-right corner. (Hint: Use backtracking)

// Function to return all possible paths from the top-left
// corner to the bottom-right corner of a 2D array
vector<vector<int>> findPaths(vector<vector<int>>& arr)
{
// Vector to store the paths
vector<vector<int>> paths;

// Call the backtracking function
backtrack(arr, 0, 0, paths);

// Return the vector
return paths;
}

// Backtracking function
void backtrack(vector<vector<int>>& arr, int row, int col, vector<vector<int>>& paths)
{
// If the row and column indices are equal to the size
// of the array, we have reached the bottom-right corner
// and can add the path to the vector
if (row == arr.size() - 1 && col == arr[0].size() - 1)
{
paths.push_back(arr[row][col]);
return;
}

// Check if the row and column indices are valid
if (row >= 0 && row < arr.size() &&
col >= 0 && col < arr[0].size())
{
// Add the current element to the path
paths.push_back(arr[row][col]);

// Call the backtracking function
backtrack(arr, row + 1, col, paths);
backtrack(arr, row, col + 1, paths);

// Remove the last element from the path
paths.pop_back();
}
} 

#### Create a function that takes in a binary tree and returns all possible paths from the root to the leaf nodes. (Hint: Use backtracking)

// Function to return all possible paths from the root
// to the leaf nodes of a binary tree
vector<vector<int>> findPaths(TreeNode* root)
{
// Vector to store the paths
vector<vector<int>> paths;

// Call the backtracking function
backtrack(root, paths);

// Return the vector
return paths;
}

// Backtracking function
void backtrack(TreeNode* node, vector<vector<int>>& paths)
{
// If the node is null, we have reached the end
// of a path and can add the path to the vector
if (node == nullptr)
{
paths.push_back({});
return;
}

// Add the current node to the path
paths.back().push_back(node->val);

// Call the backtracking function
backtrack(node->left, paths);
backtrack(node->right, paths);

// Remove the last element from the path
paths.back().pop_back();
} 

#### Create a function that takes in a string and returns all possible subsequences of the string. (Hint: Use backtracking)

// Function to return all possible subsequences of a string
vector<string> findSubsequences(string s)
{
// Vector to store the subsequences
vector<string> subsequences;

// Call the backtracking function
backtrack(s, 0, subsequences);

// Return the vector
return subsequences;
}

// Backtracking function
void backtrack(string s, int index, vector<string>& subsequences)
{
// If the index is equal to the size of the string,
// we have reached the end of the string and can
// add the string to the vector
if (index == s.size())
{
subsequences.push_back(s);
return;
}

// Loop through the string and remove each character
// at the current index
for (int i = index; i < s.size(); i++)
{
// Remove the character from the string
s.erase(i, 1);

// Call the backtracking function
backtrack(s, i, subsequences);

// Add the character back to the string
s.insert(i, 1, s[i]);
}
} 

#### Create a function that takes in a 2D array and returns all possible subsets of the array. (Hint: Use backtracking)

// Function to return all possible subsets of a 2D array
vector<vector<int>> findSubsets(vector<vector<int>>& arr)
{
// Vector to store the subsets
vector<vector<int>> subsets;

// Call the backtracking function
backtrack(arr, 0, 0, subsets);

// Return the vector
return subsets;
}

// Backtracking function
void backtrack(vector<vector<int>>& arr, int row, int col, vector<vector<int>>& subsets)
{
// If the row and column indices are equal to the size
// of the array, we have reached the end of the array
// and can add the subset to the vector
if (row == arr.size() && col == arr[0].size())
{
subsets.push_back({});
return;
}

// Check if the row and column indices are valid
if (row >= 0 && row < arr.size() &&
col >= 0 && col < arr[0].size())
{
// Add the current element to the subset
subsets.back().push_back(arr[row][col]);

// Call the backtracking function
backtrack(arr, row + 1, col, subsets);
backtrack(arr, row, col + 1, subsets);

// Remove the last element from the subset
subsets.back().pop_back();
}
}