Learn How to Solve Coding Interview Backtracking Problems

Backtracking is an algorithmic technique that is often used to solve complicated coding problems. It considers searching in every possible combination for solving a computational problem. Coding interview problems can sometimes be solved with backtracking.

We released a full course on the freeCodeCamp.org YouTube channel that will teach you how to solve backtracking problems.

Lynn Zheng teaches this course. She is a software engineer at salesforce and an excellent teacher.

You will learn general principles and also learn to solve two LeetCode hard problems in this crash course.

Watch the full course below or on the freeCodeCamp.org YouTube channel (1-hour watch).

Transcript

(autogenerated)

Lynne is a software engineer at Salesforce and an excellent teacher.

In this course, you will teach you how to solve backtracking problems, which are common in coding interviews and challenges.

Hi, everyone.

I'm Leanne.

I'm a software engineer, hobbyist game developer and a recent graduate from the University of Chicago.

Welcome to this course on solving backtracking problems.

Whether you're new to coda interviews, or already have experience with backtracking problems, this is the crash course for you.

We will learn about an all purpose template that helps you solve any kind of backtracking problems, and we will apply the template to the ko problems, like the eight queens problem, or does Sudoku solver problem.

This is exactly the template that I use for my coding problems when I'm developing algorithms for my games, or even once in my research on a non convex optimization problem.

I hope you're excited and let's dive right into this versatile template.

You can find this template in my GitHub just links to in the video description below.

Let's start with some keywords and concepts in backtracking problems that will help us understand the template better.

The first keyword sticked.

Essentially, a backtracking problem is asking you to find a valid state.

Take the N queens example that we will solve later in this video.

An example of a state is just arbitrarily placing n queens on an n by n board.

For example, here we are placing four queens on a four by four board.

On the contrary, an example of a valid state requires that the queens are placed in a fashion that they cannot attack each other.

If you aren't familiar with the rules of chess, don't worry.

The myths of queens are pretty straightforward.

A Queen can move horizontally, vertically, or diagonally.

Therefore, for replacement of the N queens to be valid, they can't stand on the same row, the same column or the two diagonals.

So how do we construct a valid state like this? Well, we build up from previous states.

Suppose we're starting from a blank and by an board where no queen is present, we can put our first Queen arbitrarily, wherever we want.

Let's say we put it here.

Then where can we place a second query, you can see now our choices are limited.

Or in background terminology, our candidate states are limited.

Because we placed the first Queen here, this entire column, this entire row, and the two diagonals are not available for new queens.

Let's say we just put the second Queen here where it's available.

Next, we try to see where we can fit in the third queen.

Our candidates are now more limited because we put the second Queen here, this column, this row and this diagonal is not available.

So our third Queen can only go here.

Finally it let's place the fourth queen.

Because this third queen is here, it blocks this diagonal and this row and this column, leaving our fourth queen to set here.

Great.

Now is this global layout a valid solution such that no Queen can attack each other? Well, we've already seen in our checks.

So like this, we have found a valid solution to this end Queen problem.

As a counter example, consider if we placed the first two queens like this.

Now, all these cells marked in red are all available, and we only have one left for the third Queen and know where to place the fourth queen.

This means that the success of state searches fails to lead to a valid solution.

And this is pretty much it about states, identifying candidates to build the next state and validating a final solution.

Now let's look at how these procedures are defined in our template.

There are four functions in our template.

The first three, as well as state candidates, search our helper functions.

The last and most important one, so is the entry point to our program.

The sole function is indeed the one that a little problem is asking you to write.

It is responsible for returning the valid solutions.

Let's look at a helper functions one by one.

This valid state this function takes a state and returns a Boolean.

It validates whether a state can be used as a final solution in our queens problem State is a validated solution.

If all n queens are placed on a board, and none of them can attack each other, get candidates.

This function finds a list of candidates that can be used to construct the next state search.

This is a recursive function.

It caused the previous two helper functions and checks if the state is a valid solution to our backtracking problem.

If it is, it records the solution by making a deep copy of this state.

Note that we do need a deep copy self a shallow copy, because we will continue to modify the state as our search goes.

But we need a static snapshot of the valid state here.

This line of return is commented out, because depending on the nature of the problem, we might need to find all valid solutions or just one.

If we only need one, we can return as soon as we have find it.

Otherwise, we continue on until we exhaust all the possible search states.

Continue down here.

If the state isn't yet a valid solution, we find candidates to build the next state.

Recall that candidates return a list of candidates.

For each one, we add the candidate to the state.

In a quiz problem.

For instance, suppose our state only contains the position of the first queen.

Here we add a candidate position for the second point.

Now we'll take this modified state and recurse on it by calling the search method on this modified state.

If the modified state is valid, the solution is recorded.

Like here, otherwise, the search function fetches candidates for this modified state and recurse.

Further, eventually, for some state, there is no more possible candidate.

Think about the example where we cannot place a fourth going anywhere, because all the spaces have been occupied.

After returning from the recursive search, we restored a modified state to the original by removing the candidate from the state.

Again, the Queens example, we undo the placement of the second query.

And now we only have the first query as well.

So it starts with an empty list of solution and an empty state.

It costs search on a state and this list of empty solution.

Search will eventually fill up this list of empty solutions, and then return the list of solutions.

And remember, this is the function that the code problem is asking us to write.

We're using this template keeping might not this is only a template.

So your helper functions, as well as state get candidates, they might taking additional parameters.

Search might also return a Boolean indicating whether a solution has been found and returned early if there is one and only one valid global solution, like in a Sudoku problem that we will eventually see.

This concludes our brief introduction to the template.

Next, let's solve the Queens problem hands on in the code.

Here we are only code number 51 the N queens problem which is Alico heart problem.

Let's first read the problem statement, given an integer, and we want to return all the distinct solution to the n queens puzzle, and we may return to answer in any order.

And lico has a specific format for us to represent the board.

For four crease example, these are the two valid solutions.

And here with the notes, not the first square on the first row is not occupied, the second square is occupied by a queen, the third one is not occupied, the fourth one is not occupied.

And on the second row, the first three squares aren't occupied, and the last one is occupied by Queen, so on and so forth.

And in the case where n is one, the Queen can only be on a single grid.

So that's the solution.

Before jumping to the code, let's first think about how we may represent this problem.

Logically.

We might be tempted to represent this board data structure as a 2d array, but it's actually a little bit waste of space do so.

Since no queens can be on the same row or the same column, we may just keep a one day list that tracks the Queen's position in each row.

Concretely, for this example here on the left, well the first row, the queen is in the second cell, so the first index is one.

For the second row, the index is three, since the queen is in the fourth cell, and this here is zero.

This here is two, following the same logic.

For the example on the right, the first index is two, the second index is zero, the third one is three, and the last one, one, because the third cell, the first cell, the fourth cell, and the second cell.

So this is the way that we represent each state as a 1d list.

For this backtracking problem.

Now I'm going to grab my template and put it into the code.

I'm going to move the surf method on top.

As already mentioned, the surf method is basically the one that the code is asking us to write.

So for the soap and Queens problem, we'll just be adapting the soap function to solutions is initially an empty list, because we may return all the valid solution in any order, then my starting state is just an empty list because we haven't placed any of the Queens into the board just yet.

Now we call self dot search on this date, given it all a list of solutions to append to and the parameter n for the N queens.

After the search is complete, we return to solutions.

Let's go ahead and remove this part.

Great.

Now we will write that as well as state function, it will take as parameter self, state and add for state to be valid, it needs to put all n queens onto the board.

So if the length of the state is n, then we know we have already put all n queens onto the board.

As for the condition where no queens can attack each other, we will handle it in the get candidate function.

Essentially, we will only return candidates that meant all valid scores that won't be attracted by the previously placed queens self state.

Great.

So here we are constructing candidates based on the state that were given.

If there's no state, meaning that we're starting from a blank board, we may place the first query anywhere we want.

So if not state, we return all the possible indices.

If the state is not empty, we find the next position in this state to populate position as the length of the state.

If we already placed the first Queen, we want to place the second query.

So candidates initially start from all the indices and then we prompt down candidates that aren't valid.

I'm using a set because it's better than walking through a list and set guarantees uniqueness.

Alright, prone down candidates that place the Queen into attacks.

So for row column enumerate state with discard the discard of column index if it's occupied so candidates that this part recall that our state is recording the column index for each row.

Now we discuss the diagonals.

So this test is the distance between the position and a row index.

Because we're trying to put a queen in the second row, now that we have already filled in the first row, we want it in the place that cannot be attacked by the first Queen diagonally.

So this one is out of the question.

And this is column plus distance.

This one is also out of the question and column minus distance.

And at the very end, we return candidates.

Now let's define our recursive search function is your take states solution solutions, and we just adapt the template.

So if self.is valid state state, and we just add it to the solutions, and return.

Otherwise, if we come down here, for candidates, a salt candidates state, and we recurse.

Because our state is in list and no longer is set, we do append candidate, and then call self dot search, state solutions, and it and then to restore the modified state back to our original repop the last entry.

Great.

So this here is the only thing that we need to take care of, because lico wants us to output strings.

And here we have is a list of column indices.

So let's define some additional helper functions here.

State to string state, we expect the output to be just like here.

So here's how we convert our list of indices.

To this output stray specified lightly code, total return is just a list for I am state because one means that the queen is in the second cell and the other cells are empty, we just append the strings for the empty cells as well as a string for the Queen's code cat knows together to get the return value.

string is this dot meaning the empty square times i plus the Queen's position was the remaining empty cells.

And rats straight.

were returned direct.

And here is self solution at Penn State copy.

We do state string and string is produced by self dot script to string sticked.

Great.

Let's now run the example code to see how we did.

Alright, cool.

Looks like our output is accepted.

Let's submit and see whether we can pass all the test cases Great, you can see that our runtime is better than almost 70% of the submissions and also some memory usage is better than 7% of the other submissions.

We are definitely using some memory because of the recursion, but that's totally okay for backtracking problems.

Next, we'll solve another lico heart problem called the Sudoku solver problem.

We're now only co problem 37 the Sudoku solver problem, which is a hard problem.

If you don't already know what a Sudoku puzzle is, you can read the description.

So a Sudoku solution must satisfy all the following rules.

Each of the digits one to nine must occur exactly once in each row.

And each column.

Also a nine of the three by three sub boxes of the grid, and liko use the dot character to indicate empty cells.

So for example, here, the code wants us to write a program that fills out this Sudoku puzzle.

In a valid way, the board is represented as a 2d array of strings, some maybe numbers, some empty cells, and lico wants us to solve the problem and modify the board in place.

The constraints are not because it's a Sudoku problem, the shape is nine by nine.

And each cell is either a digit string or the empty string.

And it's guaranteed that the input board has only one solution.

So we may return early.

If we find only one solution.

Let me copy paste my template and jump into the problem.

Alright, so again, we adopt the soak function like this, because it asked us not to return anything and just modify the port in place, I think we'll just need to do socket search board.

And then we get rid of this little function.

I'm going to have to define some constants here.

So the shape is nine by nine.

Grid length is three by three, if we're trying to validate the sub boxes, and empty is represented as this dot here.

And all the digit strings are like false.

So screen number four number in range.

One shape, plus one.

So this gives us the strain from one to nine.

And I'm going to wrap it in a set, because the order is not important.

And I know I'm going to need this when I'm traversing the Great.

Great.

So let's start by writing that is valid state function.

So it should take self and the board and check if the board is a valid solution.

So let's validate all the rows first.

For row a, I'm going to just define some helper function later down.

So let's do first soft get rows, which returns each row of the board one by one.

If, if my row is equivalent to all the digits, that it's a valid row.

Otherwise it's an invalid row and tire board is not valid.

If not set row is equal to soft digit.

return false validate.

Similarly we validate the columns calls return false.

Or Lastly, we'll validate the sub boxes.

For grid, grid, or.

And if all the rows are validated, all the columns are validated and all the grids are validated without causing this false return already, we return true meaning that the board is not a valid solution.

Now let's write to get candidates.

So self board a row and the column I'm using a row and the column because for a cell, I want to know which row and which column it is all to determine what digits have already be used, and what are left for us to use as a next state.

So used digits is a set of digit.

And I'm going to remove used remove digits used by the same row.

So used digits dot update self dot get row, this is another helper function that I will define later down digits used by that same column.

So used update self dot get column four, and the column removed digits used by the same by that by the three by three sub box budgets, update get graded roll column.

So we need to identify for an arbitrary sell which grid is on board roll call.

And lastly, because we might have already used empty string, here, when we are doing the updates, we subtract those from our use digits.

Empty is the constant that were defined for the empty string.

And candidates are just whatever that's left for us to use.

So that all useless and that concludes our get candidates function.

Now, we are moving on to do search.

Because we only have one single solution, we don't need it the list of solutions here.

So, so forth.

We have Isabel at stage.

So if self.is valid state board we return true solution.

Otherwise, we find the next empty spot and take a guess.

So for row index row enumerate or four column index, the actual element enumerate row.

If the element is the empty string, so soft, that empty for if this is empty, find can dates to construct an X ray.

Next fate candidate a self dot get candidates board.

Now that we have the row index and column index, we pass those a, we modify the board in place as the problem instructed us to do.

So.

candidate, remember that candidate is just one of the digit string.

And because here our search returns a Boolean, if one of the search actually finishes, that means that the board has been modified in place, and our problem is solved.

So it's solved is now equal to self dot search.

And just to add some comments here, we recurse on the MADI side.

If so, if so, now we just return to meaning that the entire search has completed.

Otherwise, we all do the wrong guess.

And start anew.

So we make this entry back into the empty screen that it was.

And down here we have exhausted all the candidates.

But no solves the problem.

We return false because this is an invalid succession of searches.

And if no empty spot in the first place that will just return.

Now we can get rid of this boilerplate code from our template.

Now the structure is pretty much clear.

And all I need to do is to fill a those helper functions.

helper functions for retrieving rows, columns and groups.

So here are my helper functions for retrieving rows, columns and grids.

This is pretty straightforward because our board is just a 2d array.

And to retrieve the cape row, column, or grid at our center row and column indices, we are basically just doing some really smart indices and sometimes relying on the power of either tools.

I will post my complete code on my GitHub link to in the description so you can digest those helper functions on your own.

Now let's run the code and see what we get.

Great, our output is accepted that submit and test it against all the test cases.

Awesome.

With this template, we still to lico hard problems.

To recap a backtracking problem is all about finding valid states.

To so far valid state, we identify candidates that satisfy the problem constraint and use them to build upon our current state.

Once a modified state is valid, we added as a final solution.

Now that we have sub two problems hands off, let's take another look at our template.

Recall that we have these four functions, as well as state is a helper function with a Boolean return value that validates whether a given state is final solution.

Get candidates is another helper function returning a list of candidates satisfying the problem constraint based on our current state.

Search is a recursive function or cost the two helper functions as well as state and get candidates and recurse on itself.

Lastly, solve is the function another lico problem is asking you to write it does nothing fancy other than initializing an empty list of solutions.

And then to state and colleagues search on them.

For more practice problems on backtracking, go to leak co.com and intacs search for backtracking.

This filters out a list of questions that all shares a backtracking idea.

You see, we already solved Sudoku solver, and n queens.

If you're looking for a medium hard problem, I recommend the subsets problem.

This is about finding all possible subsets or power sets often given an integer array.

It is pretty easy to identify a backtracking problem when we are asked to find all possible solutions and may return a solution in any order.

As you can see, in my submission details, I soaked the subsets problem using the exact template.

As you go through more and more legal problems, and test how much you understand about the template, you will be better prepared to identify a backtracking problem once you encounter one in your coding interviews.

This concludes our video and the only Crash Course you ever need for solving backtracking problems on your coding interviews.

For more content like this, please subscribe to my YouTube channel links down below.

I also post form project tutorials at my game development demos on my channel.

My latest tutorial is about building a discord AI chat bot with the personality of your favorite character using entirely cloud based technologies and I'm sure you will enjoy it.

Thanks for watching and best of luck preparing for coding interviews.