In backtracking algorithms, you make a sequence of decisions. Every recursive call will make one decision, and will take as an input something representative of all our past decisions. Sometimes we need all the past decisions. Sometimes only the last one. Sometimes the parity of all our previous decisions, etc.
So in summary:
- We are making a sequence of decisions (ordering being important).
- Every recursion takes as its input:
- Some indication of the state or the remaining work to be done
- Something representing prior decisions (not always).
When we design new recursive backtracking algorithms, we must figure out in advance what information we will need about past decisions in the middle of the algorithm. If this information is nontrivial, our recursive algorithm might need to solve a more general problem than the one we were originally asked to solve.
Once we’ve figured out what recursive problem we really need to solve, we solve that problem by recursive brute force: Try all possibilities for the next decision. As an example, to find the median, design an algorithm to find the element of rank \(k\).
Often, it’s easy to write an algorithm that passes in sub-portion of a list (e.g. A[k:]), but beware that this may be quite expensive. Always try to formulate your algorithm to pass indices.