Backtracking
Backtracking is a general method of recursively trying all possible solutions for the problem.
Of course, the number of all possible solutions can be very large, so this method is usually only applicable when the input of the problem is not too big, and when there is no better algorithm. On the upside, pretty much any problem can be solved with backtracking, given enough time – just try all possible solutions!
The best approach to learn backtracking is probably to try several classical problems, and see their solutions.
The following problem is a great example of an easy backtracking problem. Try to solve it yourself, and then be sure to read the solution to understand all details:
Runtime of backtracking
It's not very easy to calculate the time complexity of recursive functions in backtracking. One piece of advice would be to estimate how many possible states the function has, and how much work it does in each state.
In the subsets problem above, each state has some subset of all numbers (currentSubset), and an index of the current position in the nums array. If we say length of nums is N, then there are N possible indexes for the current position, and 2^N possible current subsets (each number can be either included or not), so we can estimate the upper bound on the number of states as O(2^N × N).
If we are at the terminating case, we print the subset. We have total 2^N subsets, and their length is at most N, so we have upper bound of O(2^N × N) on the total time to print all generated subsets.
Finally, when we are not at the terminating case, all we do in the function (except recursing) is add and remove element at the end of the list, so we spend O(1) time on this in each state, and O(2^N × N) total in all states.
This way we can estimate an upper bound on the total runtime as O(2^N × N). In fact, you can calculate this more precisely (math involved), and you will get the same result.
As for the space complexity, you can note that we store all the subsets in the result, so it will also be O(2^N × N), again because we have 2^N subsets, and each of length at most N.
In this problem, and in similar ones, you can try to calculate runtime precisely, but it will usually be math-heavy and complicated. Estimations like these, based on the number of states and the work in each state, usually provide good enough results, and are much easier to carry.
More practice problems
Let's solve some more practice backtracking problems.
In the following problem, you have to generate all correctly matched sequences of N pairs of parentheses. Try to solve it on your own, and then see the solution to learn more:
In the following problem we generate all permutations of length N. As you know, the number of permutations of length N is N! – already a big number, so backtracking seems to be appropriate here.
Let's solve a more difficult backtracking problem. In the following one, you need to find a word in the grid of characters, and backtracking is a great solution here.
Further reading
Want to read more about backtracking? You can check out the chapter on complete search and backtracking in Competitive Programmer’s Handbook.
Even more practice problems
Here are some more good backtracking problems to practice:
