Backtracking in C++

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

// 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]); 
    } 
} 

// 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(); 
    } 
} 

// 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(); 
} 

// 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]); 
    } 
} 

// 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(); 
    } 
}