Backtracking Template

Prereq: DFS with States

Combinatorial Search Problems

Combinatorial search problems involve finding grouping and assignments of objects that satisfy certain conditions. Finding all permutations/subsets, solving sudoku, and 8-queens are classic combinatorial problems.

Permutations

It's important to review basic high school combinatorics to get an intuition for combinatorial problems.

Permutation means arranging things with an order. For example, permutations of [1, 2] are [1, 2] and [2, 1]. Permutations are best visualized with trees.

The number of permutations is given by n! (we looked at factorial in Recursion Review). The way to think about permutation is to imagine you have a bag of 3 letters. Initially, you have 3 letters to choose from, you pickone out of the bag, now you are left with 2 letters, you pick again now there's only 1 letter. The total number of choices is 3*2*1 = 6 (hence we have 6 leaf nodes in the above tree).

If you want to learn more about the math, you can find more details in the Wikipedia entry.

Complexity

The complexity of combinatorial problems often grows rapidly with the size of the problem. For example, as we have seen the number of permutation of 3 objects is only 6. However, number of permutation of 10 objects is about 3 million. The number of permutations of 11 objects is about 40 million. The rapid growth of solution space with even a small increase in problem size is called combinatorial explosion.

Combinatorial Search == DFS on tree

In combinatorial search problems, search space is in the shape of a tree. The tree that represents all the possible states is called a State-space Tree.

Each node of the state-space tree represents a state we can reach in a combinatorial search (by doing a particular combination). Leaf nodes are the solutions to the problem (permutations in the above example).

Combinatorial search problems boil down to DFS/backtracking on the state-space tree.

Since the search space can be quite large, we often have to "prune" the tree, i.e. discard branches.

Three Steps to Conquer Combinatorial Search Problems

We summarized a three-step system to solve combinatorial search problems:

  1. Identify the state(s).
  2. Draw the state-space tree.
  3. DFS/backtrack on the state-space tree.

In step 1, we want to answer the following two questions to identify the states:

  1. What state do we need to know whether we have reached a solution (and using it to construct a solution if the problem asks for it). In the above permutation example, we need to keep track of the letters we have already selected when we do DFS.

  2. What state do we need to decide which child nodes should be visited next and which ones should be pruned. In the above permutation example, we have to know what are the letters left that we can still use (since each letter can only be used once).

For step 2, you want to draw the tree. A small test case that's big enough to reach one solution (leaf node).

For step 3, apply the following backtracking template

function dfs(node, state):
    if state is a solution:
        report(state) # e.g. add state to final result list
        return

    for child in children:
        if child is a part of a potential solution:
            state.add(child) # make move
            dfs(child, state)
            state.remove(child) # backtrack

Notice how very similar this is to the Ternary Tree Path code we've seen in DFS with States module. That problem has an explicit tree. For combinatorial search problems, we have to find our own tree.

This all may sound very abstract at the moment. It will be super clear once we apply the system to a couple of real problems.

In the next module, we will apply this system to solve concrete problems.