Some combimnatorial problems require a specific technique called backtracking. The common problems in this category are permuation, combination and subsets. Backtracking is a general algorithm for finding all (or some) solutions to some computational problems, that incrementally builds candidates to the solutions. As soon as it determines that a candidate cannot possibly lead to a valid complete solution, it abandons this partial candidate and “backtracks’’ (return to the upper level) and reset to the upper level’s state so that the search process can continue to explore the next branch. Backtracking always work in recursive functions. Here I want to emphasize one aspect of applying backtracking to these problems: the ordering.
The ordering in the current context is referring to the order in which the the items are listed to form the final product. For some problems, this order is not important; while for others, the order matters. In other words, to the former, all items forming only one list; in the latter, different orderings give different lists althoug the items in the lists are all the same. This ordering difference determines that whether we can use a trick to reduce amount of redundant computations in the recursive/backtracking solver.
Let's use some examples to illustrate the idea.