Backtracking

Backtracking algorithms heavily use DFS¹ to enumerate all the possible solutions to a problem. These candidates are expressed as the nodes of a tree structure, which is the potential Search Tree [1].

Examples

The Subsets is a classic problem suitable for Backtracking.

At each call, we can decide whether or not to include the current element. This decision requires two different function calls that will derive the following Search Tree from the input [1, 2, 3].

If we collect the results of the 8 leaf nodes, we will get all our subsets.

Analyze the Complexity

The Time Complexity is proportional to the number of nodes in the Search Tree, multiplied by the amount of work we do in each call.

We can use the formula $|children{|}^{height}$ to derive the number of nodes. If we apply this formula to the previous problem, we get $|children|=2$ and $height=3$, where the height is actually the number of nodes in the input. Plus, we need to consider the work we do to append the solutions to the final result list, which is an additional $O(n)$ time. This would make the entire complexity to $O(n\cdot 2^n)$.

The Space Complexity is proportional to the height of the Search Tree. In fact, once we reach a leaf node, we simply terminate our search and go back to the parent nodes.

References

• [1]: https://en.wikipedia.org/wiki/Backtracking