Backtracking

Not all those who wander are lost.

Table of Contents

  • Introduction
  • What is Backtracking?
  • Various Subtle Variations in Backtracking Problems
  • Examples
  • General Framework / Template
  • Problem Solving
    • Leetcode #17: Letter Combinations of a Phone Number
    • Leetcode #22: Generate Parentheses
    • Leetcode #39: Combination Sum
    • Leetcode #40: Combination Sum II
    • Leetcode #46: Permutations
    • Leetcode #78: Subsets
  • Summary

Introduction

If you feel not-so-comfortable with the concept of recursion, I strongly recommend checking out my other post on the topic. Backtracking heavily uses recursion, so it’s important that you are comfortable with it.

Let’s consider an example from our day to day lives. When you are in your house ready to go out and you are not able to find the key to your car. You don’t know what room you lose the key in. You start with your living room, check the key holder, you don’t find it. You then check near the sofa, near the TV, near the chair you sat on. You don’t find it, so you check the kitchen. You check near the dining table, near the stove. You then go to your study room, you check your backpack, you check on your table and you finally find it in the drawer. So you don’t check near the bookshelf, nor do you check in your bedroom anymore. The process that you followed just now is what backtracking is. 

What is Backtracking?

If you want to map the above procedure to a computer science problem, here is how the problem would look like –

Finding a key in the house using backtracking approach example.

The numbers denote the sequence that you follow – first you enter the living room, go near the key holder, come back, then go near the sofa, come back, and so on. That’s exactly what backtracking is. The process that you followed was of trying out all the possibilities and until you find what you are looking for. If we talk in computer science terms, you start at the root (house), visit the children and their children until you hit the leaf node. If at a leaf node, you didn’t find the key, you take a step back and then move to another branch of the subtree. The name “backtrack” comes from the fact that we test one possibility (one branch), then take a step back, and then test another possibility until the terminating condition is hit i.e. finding the key, in this case.

Recursion makes exploration of all paths/branches of the tree very easy. At any time you only have to think about the current level and recursively call the function for exploring the children. Whenever you have a recursive code, you should always think about the base case where you will terminate the recursion. Depending on the problem it would, of course, differ. For the above example, the terminating condition can be “Is the current node the key?” (currentNode == key).

Various Subtle Variations in Backtracking Problems

Now you know what backtracking is. There are a few variations that you should be aware of –

  1. Like the above example where you were searching for one thing and that is all that you cared about. There was only one key and you didn’t check if there are more keys anyway.
  2. The second variation as you might have guessed by now is when there are multiple possibilities that take you to the thing that you are looking for. Like, there are multiple keys in your house and you pick the one that you find earliest and leave the house.
  3. In the third variation, there are multiple possibilities and you care about all of them. For example, there are multiple keys and you want to have all of them (like you would want the duplicate key to be with you as well, just in case).
  4. The fourth variation is a bit different than the above three. In all the above variations, all that you cared about is the end goal i.e. you only cared about the key or keys, but you didn’t care about the “how” part of your search i.e. you didn’t care about how you found the key. You may want to know the root to leaf path as well, like the way you would want to remember where you found the key so that next time you will directly check house –> study room –> table –> drawer instead.
  5. The fifth variation builds on top of the fourth where you want to know all the paths where you found the different keys.
  6. This variation is again a bit different than all the above 5. In this, you are not necessarily looking for something, but you are just taking a look into what is all there to look. For example, say you want to list down all the places where you should check for your key. In the above example, it would look something like the key holder, sofa, TV, chair, dining table, stove, backpack, table, drawer, bookshelf, bed, dressing table, wardrobe.
  7. The seventh variation can be built on top of the 6th where you also want to save all the paths along with the things.

Examples

Let’s see some real programming questions where the above variations can be applied.

  1. You want to know whether a number exists in the given binary tree.
    This fits perfectly in the variation 1. You will check each node in the tree and the moment you find the number, you will stop and return true.
  2. You want to make a set of all leaf nodes in the tree.
    This is variation 3: You are looking for leaf nodes and there can be multiple of them, you want to know all of them. You will start from the root and go all the way down and check if it is a leaf node, add to the set that you will return at the end.
  3. You want to print all root to leaf paths in the tree.
    This is variation 5. You are looking for leaf nodes but at the same time, you want to know and save the path as well. You will start at the root and keep track of the path from the root to the current node. Initially, it would be just the root but as you go down in the tree, you will add the then-current node into your path. Now whenever you hit a leaf node, you will add the then-current value of path into your list of paths that you will return at the end. Remember to remove the added node when you go up a level (backtrack) after the exploration of the subtree. We will see this in action in code.

All the above examples directly mentioned the tree structure. Sometimes it is not so obvious.

Can you spot a tree structure when solving the sudoku puzzle?
(Those who don’t know about Sudoku. Sudoku is a grid of size 3 X 3 where each cell itself is a grid of size 3 X 3 which makes a total grid of size 9 X 9. The goal is to have 1 to 9 numbers appear exactly once in each row of size 9, each column of size 9, and each grid of size 3 X 3 i.e. 9 again. Some numbers are already provided at the beginning which you can not erase and your task is to fill the right numbers in the black cells in the 9 X 9 grid.)

Some things to think about –

  1. For each empty cell, what are the possible numbers that can take that cell? The answer can be anything from 1 to 9 i.e. {1, 2, 3, 4, 5, 6, 7, 8, 9}.
  2. Now what numbers will certainly not be there? The numbers provided in the beginning can help here. As we don’t want to repeat a number, the numbers that are present in the same row as the empty cell, can be removed from the possibilities set. Similarly, the numbers in the same column and the same 3 X 3 grid can also be removed. Say you end up with {2, 4, 5, 7} which is a set of valid possibilities at this time.
  3. Now you assume one number to be the correct one, say 2.
  4. You now find the next empty cell, find possibilities for that cell, assume one, and so on until you reach one of the two conditions –
    1. You have filled the entire grid already, so there are no empty cells. Yay, you solved the puzzle. Because you were always finding the valid possible values for each empty cell, we don’t have to worry about violating the rules. You found one solution for the given Sudoku puzzle and now you can stop. (If you want to know all the possible solutions, you won’t stop here).
    2. You reached an empty cell where there are no valid possibilities. All numbers already appear in the same row, column, or the grid as the current empty cell. This means that one of our assumptions was incorrect (assuming there exists a solution to the given puzzle). 
  5. If you hit an empty cell that can’t be filled, you made a mistake along your way. You will try the next valid possibility for the empty cell before the current empty cell. 
  6. Likewise, if you have explored all possibilities of an empty cell and discover that you can’t solve the puzzle, you will come back to the previous empty cell and change the assumption there.

Here is how the tree structure, in this case, would look like –

Backtracking Sudoku Puzzle Solving Example
Backtracking Sudoku Puzzle Solving Example

When solving the puzzle, you indeed care about the path i.e. choices you make for each cell. If you want just one solution, then this problem would be under variation 4. If there are multiple solutions possible for the given puzzle and you want to explore all of them, then it can be considered variation 5.

Let’s take a look at another problem where you want to find all ways in which you can make a sum of N using the given set of numbers.
For example, sum 10 can be made using {2, 3, 6, 8, 10} in 2 ways – {2, 8}, {10}.

Can you find the tree structure here? Before that, are you able to think of how you can solve this problem?

  1. There are two possibilities for each number – you choose the number to be a part of the total sum 10, or you don’t.
  2. Then move on to the second number and repeat the procedure.
  3. If you hit a point where you can’t pick any number as a possible number to be a part of the total sum i.e. when all numbers are greater than the required sum, you go a level up (backtrack) and explore the other possibility.

Here is how the tree structure would look like –

Make sum N tree diagram.

General Framework / Template

If this has given you enough idea about backtracking let’s take a look at some problems on Leetcode that involve backtracking.

Wait for a second, just before that, keep in mind the following general framework for the backtracking problems.

Remember that the backtracking problems are usually going to get solved using recursion and hence you will have to think about the base case. For the Sudoku example, the base case can be, are there any empty cells left? If not, then the puzzle is solved. If there is an empty cell but we have explored all possibilities for that & didn’t find the answer, or there are no valid possibilities for the cell, then we can say either something was wrong in previous steps or the solution does not exist. Similarly, for the “choosing numbers to make sum N” example, the base condition can be whether we reached a negative value for N? If yes, then there is some mistake made in the previous steps. If N is 0, then we have found a valid set of numbers to make the sum N. Likewise, the base conditions would differ for different problems but they are very similar to each other most of the time.

For variation 1 (or 2) –

  1. Start
  2. Base Condition
  3. Find all possibilities for the current state.
  4. For each “possibility”:
    1. Assume the current state to be this “possibility”.
    2. Solve the problem recursively.
    3. If the problem is solved, note the solution and return from here.
    4. If the problem couldn’t be solved, it means that this choice of “possibility” was not right. 
    5. Continue the loop.
  5. Reaching here means that the problem couldn’t be solved.

For variation 3 –

  1. Start
  2. Base Condition
  3. Find all possibilities for the current state.
  4. For each “possibility” –
    1. Assume the current state to be this “possibility”.
    2. Solve the problem recursively.
    3. If the problem is solved, note the solution but don’t return from here
    4. If the problem couldn’t be solved, it means that this choice of “possibility” for the current state was not right. 
    5. Continue the loop.
  5. At this point, all possible solutions are noted already (this includes the case of no possible solutions as well, in which case the notes will be empty).

For Variation 4 –

  1. Start
  2. Base Condition
  3. Find all possibilities for the current state.
  4. For each “possibility”:
    1. Assume the current state to be this “possibility”.
    2. Add this possibility into the “path” that will keep track of all choices that you made along the way.
    3. Solve the problem recursively.
    4. If the problem is solved, note the solution, the path, and return from here. The current value of “path” will have the set of choices made at each step. 
    5. If the problem couldn’t be solved, it means that this choice of “possibility” was not right. 
    6. Remove the “possibility” from the “path”. (This will, of course, be the last value in the path).
    7. Continue the loop.
  5. Reaching here means that the problem couldn’t be solved.

For Variation 5 –

  1. Start
  2. Base Condition
  3. Find all possibilities for the current state.
  4. For each “possibility”:
    1. Assume the current state to be this “possibility”.
    2. Add this possibility into the “path” that will keep track of all choices that you made along the way.
    3. Solve the problem recursively.
    4. If the problem is solved, note the solution, the path, but don’t return from here. We still want to explore whether there are multiple solutions.
    5. If the problem couldn’t be solved, it means that this choice of “possibility” was not right. 
    6. Remove the “possibility” from the “path”. (This will, of course, be the last value in the path).
    7. Continue the loop.
  5. At this point, all possible solutions are noted already (this includes the case of no possible solutions as well, in which case the notes will be empty).

Problem Solving

Wasting no time, let’s solve some problems.

Leetcode #17: Letter Combinations of a Phone Number

  1. Here, for each number from 2 to 9, you already know the possibilities. E.g. 2 – {‘a’, ‘b’, ‘c’}, 3 – {‘d’, ‘e’, ‘f’}, and so on. So we can store that information beforehand. 
  2. When will you stop processing? You can stop once the input ends.
  3. What do you want in the end? All words that are possible. So it is a variation 5.

Let’s see the code.

class Solution {
public:
map<char, string> numToString = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"},
{'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"},
{'8', "tuv"}, {'9', "wxyz"}};
vector<string> answer;
string input;
void recurse(string path, int index) {
if (!(index < input.length())) { // the entire string is processed already.
if (!path.empty()) { // only add non-empty strings.
answer.push_back(path); // add the current value in final answer.
}
return; // nothing else to do here.
}
char currentChar = input[index];
string possibilities = numToString[currentChar];
for (char c: possibilities) { // for each possibility.
path.push_back(c); // assume current possibility.
recurse(path, index+1); // recursively solve the remaining problem.
path.pop_back(); // undo the current possibility.
}
}
vector<string> letterCombinations(string digits) {
input = digits;
recurse("", // empty string in the beginning.
0); // what index in input to start the recursion.
return answer;
}
};
view raw Leetcode_0017.cpp hosted with ❤ by GitHub

I have intentionally kept the names of the variables & functions generic so that it is easier to relate to the frameworks that we discussed earlier. Comments in the code also make it clear how easy it is to write a recursive backtracking code for any problem.

Let’s move on to the next problem.

Leetcode #22: Generate Parentheses

  1. There are only two possibilities – either to insert a ‘(‘ or a ‘)’.
  2. Base conditions – 
    1. For parentheses to be well-formed, total opening parentheses should be equal to the total closing parentheses. In addition to that, at any point (index) in the string, total closing parentheses must not exceed the total opening parentheses.
    2. Initially, we have ‘n’ opening and ‘n’ closing parenthesis.
    3. The moment we find that there is no more opening parenthesis left and no more closing parenthesis left, we can add the current value into the final answer.
  3. What do we want? All possible ways of using n number of ‘(‘ and ‘)’ such that the parentheses are well-formed. Hence, this fits in the variation 5.

Based on this, let’s see the code –

class Solution {
char openingParenthesis = '(';
char closingParenthesis = ')';
vector<string> answer;
void recurse(string &path, int unusedOpen, int unusedClose) {
if (unusedOpen < 0 || unusedClose < 0) { // invalid state.
return;
}
if (unusedOpen > unusedClose) { // path is not well-formed.
// More opening parenthesis than closing means that we used
// more closing parenthesis. This makes the path invalid.
// This condition guarantees that only well-formed parentheses
// will be pushed into the answer.
return;
}
if (unusedOpen == 0 && unusedClose == 0) { // used all parentheses.
answer.push_back(path); // add the current path into the answer.
return;
}
// Possibility 1 = '('.
path.push_back(openingParenthesis); // try '(' possibility.
recurse(path, unusedOpen-1, unusedClose); // recursively solve.
path.pop_back(); // undo '(' possibility so that we can test others.
// Possibility 2 = ')'.
path.push_back(closingParenthesis); // try ')' possibility.
recurse(path, unusedOpen, unusedClose-1); // recursively solve.
path.pop_back(); // undo ')' possibility.
}
public:
vector<string> generateParenthesis(int n) {
// Initially we have n opening and n closing parentheses that are unused.
string path = ""; // empty path in the beginning.
recurse(path,
n, // number of unused opening parentheses.
n); // number of unused closing parentheses.
return answer;
}
};
view raw Leetcode_0022.cpp hosted with ❤ by GitHub

You might have noticed, we don’t need a loop here because there are just two possibilities. 

Leetcode #39: Combination Sum

(The same number can be chosen multiple times, there won’t be any duplicates in the given numbers).

  1. For each number in the given array, we have two options/possibilities – Add that number into our path i.e. consider the number to make the target sum, or to skip this number from consideration and move on to the next number.
  2. Base conditions –
    1. If all numbers are either considered or skipped, there is nothing more to do to make the target sum.
    2. If the target sum gets into the negative range, we have considered a number that we shouldn’t have considered along the path.
    3. If the target is 0, we don’t have to consider more numbers because the current set of selected/considered numbers already make the desired sum.
  3. What do we want? Again all ways of making the target sum, so variation 5.

Let’s see the code.

class Solution {
public:
vector<vector<int>> answer;
vector<int> numbers;
void recurse(vector<int> &path, int index, int target) {
if (target == 0) { // no more numbers are required.
answer.push_back(path); // add current numbers into the answer.
return;
}
if (target < 0 || // invalid.
index >= numbers.size()) { // no more numbers left to select.
return;
}
// There are only 2 possibilities - Either to consider/select the number
// or not consider the number.
// Possibility 1 - Don't consider the number at the current index.
recurse(path, index+1, target); // move to next number.
// Possibility 2 - Consider the number at current index.
path.push_back(numbers[index]); // consider the number.
recurse(path,
index, // same number can be used again, so don't change
// the index
target-numbers[index]); // reduce the target.
path.pop_back(); // undo the consideration.
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
numbers = candidates;
sort(numbers.begin(), numbers.end());
vector<int> path; // to store selected numbers. Initially empty.
recurse(path,
0, // what index to start from.
target); // how much sum to make.
return answer;
}
};
view raw Leetcode_0039.cpp hosted with ❤ by GitHub

There is another way to look at the same problem though. Let’s say we want to create a list of numbers that adds up to the target. So what number can be the first one into the list? The first number can be anything from a given set of numbers. Similarly, the second number can be any number, and so on.

The code, in this case, would look like –

class Solution {
public:
vector<vector<int>> answer;
vector<int> numbers;
void recurse(vector<int> &path, int startIndex, int target) {
if (target == 0) { // no more numbers are required.
answer.push_back(path); // add current numbers into the answer.
return;
}
if (target < 0) { // invalid. we added more numbers than needed.
return;
}
for (int i=startIndex; i<numbers.size(); i++) { // for each possibility.
path.push_back(numbers[i]); // consider the possibility.
recurse(path,
i, // same number can be used again, so don't change
// the index.
target-numbers[i]); // reduce the target.
path.pop_back(); // undo the possibility.
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
numbers = candidates;
sort(numbers.begin(), numbers.end());
vector<int> path; // to store selected numbers. Initially empty.
recurse(path,
0, // what index to start from.
target); // how much sum to make.
return answer;
}
};
view raw Leetcode_0039.cpp hosted with ❤ by GitHub

Leetcode #40: Combination Sum II

(Each number can only be used once but there can be duplicates in the given numbers.)

As you can see, the previous problem and this one differ slightly. In the previous problem, we wanted to avoid both {2, 3} & {3, 2} from getting into the answer. For that, we sorted the input in the beginning and when calling the function recursively, we passed the current index ‘i’ as the startIndex for the recursive call. Here, we have a different problem. Because there are duplicates, even if we pass the current index ‘i’ as the startIndex for the recursive call, we might still end up having duplicates like {2, 3} and {2, 3} simply because the ‘2’ that we see in the first and second set were at different indices in the input set. For example, make a sum of 5 from {2, 2, 3}. The answer is just {{2, 3}}, but our previous solution will return {{2, 3}, {2, 3}}.

Luckily, the fix is simple. Going back one step. When we added the for loop of possibilities into the previous solution, the intention was to check all possibilities of numbers to be into our path. What we will do here instead is to consider only the unique possibilities than considering all possibilities for that position in the path.

The code would look like this.

class Solution {
public:
vector<vector<int>> answer;
vector<int> numbers;
void recurse(vector<int> &path, int startIndex, int target) {
if (target == 0) { // no more numbers are required.
answer.push_back(path); // add current numbers into the answer.
return;
}
if (target < 0) { // invalid. we added more numbers than needed.
return;
}
int previouslyChecked = -1;
for (int i=startIndex; i<numbers.size(); i++) { // for each possibility.
if (previouslyChecked == numbers[i]) { // skip if the number is
// the same as previous.
// Why skipping is the right thing to do?
// Remember that we are constructing a path.
// Path has already tried adding the number into it and
// recursively solving the problem. So there is no point in
// checking the same number again.
continue;
}
path.push_back(numbers[i]); // consider the possibility.
recurse(path,
i+1, // only consider numbers beyond i to avoid duplicates,
// otherwise {2, 3} and {3, 2} will both be added.
target-numbers[i]); // reduce the target.
path.pop_back(); // undo the possibility.
previouslyChecked = numbers[i]; // update previous.
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
numbers = candidates;
sort(numbers.begin(), numbers.end());
vector<int> path; // to store selected numbers. Initially empty.
recurse(path,
0, // what index to start from.
target); // how much sum to make.
return answer;
}
};
view raw Leetcode_0040.cpp hosted with ❤ by GitHub

A very similar approach works for the next problem as well.

Leetcode #46: Permutations

  1. What are the possibilities? 
    1. We know that, there will be n! permutations and each permutation will be of size n.
    2. Hence, we can say that for each index, there are n possibilities. Of course, we will skip the ones that are already present in the path.
  2. Base Condition
    1. If the path has size n, we have a permutation ready.
  3. What do we want?
    1. Again all paths, so it is also a variation 5.

Here is the code and you will be able to see how similar these are.

class Solution {
vector<vector<int>> answer;
vector<int> numbers;
void recurse(vector<int> path) {
if (path.size() == numbers.size()) { // all numbers are added.
answer.push_back(path); // add current permutation into answer.
}
for (int i=0; i<numbers.size(); i++) { // for each possibility.
if (find(path.begin(), path.end(), numbers[i]) != path.end()) {
// Adding same number twice would make the permutation
// invalid, so skip this number from consideration.
continue;
}
path.push_back(numbers[i]); // consider this possibility.
recurse(path); // recursively solve.
path.pop_back(); // undo the considered possibility.
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
numbers = nums;
vector<int> path; // to keep track of considered numbers
// and their order. Initially empty.
recurse(path);
return answer;
}
};
view raw Leetcode_0046.cpp hosted with ❤ by GitHub

Leetcode #78: Subsets

Again very similar other problems but a lot simpler.

  1. Possibilities
    1. At each point in the path, you can add any element that is not already added.
  2. Base condition
    1. If the starting index gets out of bound, the recursion will stop automatically, so no need for explicit base condition.
class Solution {
vector<vector<int>> answer;
vector<int> numbers;
void recurse(vector<int> path, int startIndex) {
// All paths are of course the subsets of given set because we are
// choosing the elements from the given numbers.
answer.push_back(path); // add current subset into answer.
for (int i=startIndex; i<numbers.size(); i++) { // for each possibility.
path.push_back(numbers[i]); // consider this possibility.
recurse(path, i+1); // to avoid choosing same number multiple
// times, move the startIndex by 1.
path.pop_back(); // undo the considered possibility.
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
numbers = nums;
vector<int> path; // to store the subset. Initially empty.
recurse(path,
0); // what index to start from.
return answer;
}
};
view raw Leetcode_78.cpp hosted with ❤ by GitHub

Summary

It was quite a long post, but I hope it helped you in either learning about the concept, refreshing the concept, or both. Once you understand the template, the implementation is generally not so hard. However, you have to understand that we are using the recursion quite heavily and the time complexity of the solution is quite high. Luckily, the input sizes are generally small when a backtracking solution is expected. You can also use this fact as a hint for solving problems where the input sizes are small. 

While backtracking is easy and great at solving complex problems, it sometimes solves the same problems repeatedly and this is where dynamic programming comes to the rescue. In the followup post, we will look into the dynamic programming concept and problems. Recursion, backtracking, and dynamic programming together strengthen your understanding because of their closeness. Learning one strengthens the other two and hence I strongly encourage reading or glancing over all three posts by me.

I covered a few problems in this post to give you some practical examples, what questions do you still have? Is there a specific question that you would like me to explain? Put that in the comments below. Share your thoughts about the post and what did you like, not like about the post. I am looking forward to your opinions.

Of course, don’t forget to like, share the post and subscribe to the blog.

Happy coding!


Related Posts


One thought on “Backtracking

  1. Thanks for this wonderful post! If we think of building links between the problems (variations) and also links between recursion, backtracking and dynamic programming, it makes these somewhat overwhelming concepts easier to understand.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s