LeetCode Distilled Series: 3 Simple Steps to Solve Any Backtracking problems

Backtracking is one of the most useful and yet less well-understood techniques in algorithm interviews. We find the best way to explain backtracking is through combinatorial search problems.

Combinatorial Search Problems

Combinatorial search problems involve finding, grouping, and assignments of objects that satisfy certain conditions. Combinatorial searches involve finding all permutations and subsets. We often use combinatorial problems in real life. Solving puzzles such as Sudoku and 8-queens are make use of combinatorial techniques.

Permutations

It’s important to review basic combinatorics develop an intuition for solving combinatorial problems.

Let’s look at a few basic concepts.

Permutation means arranging item in order, and looking for every possible arrangement of elements within a set. Let’s look at a simple example. If we have a basic array of [1, 2]. There are two possible ways of associating the elements of 1 and 2; They are [1, 2] and [2, 1] respectively. These grow exponentially. If we have a list of 3 elements including [a,b,c], we have 6 options: [a,b,c], [a,c,b], [b,a,c],[b,c,a],[c,a,b], and finally [c,b,a].

The best way to visualize permutations is by using 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 that you have a bag of 3 letters. Initially you have 3 letters to choose from; you pick one 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. As a result we have 6 leaf nodes in the above tree.

Complexity

As mentioned, the complexity of combinatorial problems will grow rapidly with the size of the problem. For example, as we have seen, the number of permutation of 3 objects is only 6. However, the 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, the search space is handled in the shape of a tree. A tree that represents all the possible states for of permutations within a set is called a State-Space Tree.

Each node of the state-space tree represents a state we can reach in a combinatorial search through a specific combination. A leaf nodes in a state-space represents the solutions to the problem. Each one is a form of permutation, as we demonstrated with our tree above.

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, and “discard branches.”

Three Steps to Conquer Combinatorial Search Problems

To summarize what we covered previously, we created a three-step system for solving combinatorial search problems:

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

1. Identify the state(s)

We want to answer the following two questions to identify the states:

What state do we need in order to know whether we have reached a solution (and by extension, can we construct a solution based on this state if the problem asks for it)?

In the the permutation example we used above, we need to keep track of the letters we have already selected when we do DFS.

What state do we need in order 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 letters are left that we can still use (since each letter can only be used once).

2. Draw the tree.

We should be able to handle this with small test case and that is simultaneously large enough to reach one solution or leaf node for any size set.

3. DFS on the tree

function dfs(node, state):
    if state is a solution: # is this a leaf node
        report(state) # e.g. add state to final result list
        return
    for child in children: #visit branches
        if child is a part of a potential solution:
            state.add(child) # make move
            dfs(child, state)
            state.remove(child) # backtrack

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

Finding all permutations of a string

If you like the content, read more

Algo Monster