Recursion

Backtracking

Lesson

Sometimes when you write a recursion, you'll want one of the inputs to be a Data Structure. This often happens when you're generating a lot of solutions to a problem. The thing is, the code you write will naturally be slow if the Data Structure changes at all, and you'll need to use "Backtracking" to optimize. Here's an example.

Problem: Print out every possible array combination of 0's and 1's, up to length 3. For example, [], [0], and [1,0,1] are a few of the combinations you should print.

Solution: You can solve this problem by starting with an empty array, and adding 0's and 1's to the array until you consider every possible solution to the problem. The recursion for this is to visit the current array, and then visit the array with an additional 0, and then with an additional 1. Here's the code you'd normally write for this:

This code is a traversal - it visits all the possible solutions the problem, the same exact way a DFS would visit every node in a tree. Here's a visualization of the traversal, where each node represents a function call to visitAll that gets made, along with its input arr:

This code works, but it turns out it's very slow. Every array in the above picture is a new one, which took time and space to create.

Backtracking is when you make your function's inputs global variables, so that you never re-create the same array many times. You only have one single global array that you modify, saving time and space.

Here's the same code as above but using Backtracking. Since arr is global now, we need to update it before and after every call to visitAll:

Now with our Backtracking code, we're still running the same algorithm as before, but the function doesn't have any inputs:

This saves time and space, because we don't waste time or space creating new arrays. The time and space of each function call were O(n), and now they are O(1).

Takeaways

Backtracking is when you make your Data Structure inputs global to save time and space. You update your global Data Structures before and after every function call.

To generate many solutions to a problem, you usually write a traversal and then optimize using Backtracking.

Mark as Completed:
Submits:
test
Test your code to get an output here!