[Backtracking method 1.0] Understand backtracking

The article directories

• • • What is backtracking
    • The efficiency of backtracking
    • Problems solved by retrospective Method (Five types of questions)
    • How to understand backtracking
    • Backtracking template
    • conclusion

Although the backtracking method is difficult, the backtracking method is the violent solution + pruning operation backtracking is the brute force cracking, the core competitiveness of a good backtracking algorithm lies in pruning operation, constantly optimize the efficiency of the whole brute force cracking

What is backtracking

Backtracking can also be called backtracking search, which is a way of searching.

We’ve talked about backtracking more than once in the binary tree series, for example, binary trees: the idea of using recursion is to hide backtracking.

Backtracking is a by-product of recursion, and as long as there is recursion there will be backtracking.

So in the following lectures, backtracking functions, also known as recursive functions, refer to the same function.

The efficiency of backtracking

Problems solved by retrospective Method (Five types of questions)

Retrospective method can generally solve the following problems:

1. Combination problem: N numbers in accordance with certain rules to find the set of k numbers
2. Slicing problem: A string can be sliced in several ways according to certain rules
3. Subset problem: how many subsets of a set of N numbers are eligible
4. Permutation problem: N number permutation according to certain rules, there are several permutations
5. Checkerboard problems: N queen, solving sudoku and so on

“I believe that after looking at these, you will find that every problem is not simple!”

In addition, some students may be confused about what is a combination, what is permutation?

“Composition does not emphasize the order of elements; permutation emphasizes the order of elements.”

For example, {1, 2} and {2, 1} are sets in combination, because order is not emphasized, and {1, 2} and {2, 1} are two sets in permutation.

Remember to mix out of order, arrange in order, that’s it.

How to understand backtracking

Backtracking template

The backtracking algorithm template is as follows:

In the recursion of binary trees, we talked about the recursion trilogy, and I’m going to give you the back trilogy.

First, traceback the function template return values and parameters (as in the first of the three recursive steps)

In the backtracking algorithm, my habit is to call the function backtracking, which is arbitrary.

In the backtracking algorithm, the return value of the function is usually void.

Parameters: Because the parameters required by backtracking algorithm are not as easy to determine as the binary tree recursion, it is generally written logic first, and then fill in whatever parameters are needed.

But as we go back to the problem, just to make it easier for you to understand, I’m going to help you define the parameters at the beginning.

The pseudocode of the traceback function is as follows:

Void Backtracking (parameter)Copy the code

Second, the termination condition of the backtrace function (as in the second of the previous three recursive steps)

And since it’s a tree, when we were doing recursion for binary trees, we knew that traversing a tree must have termination conditions.

So backtracking also has termination conditions.

When the termination condition is reached, you can see from the tree that, in general, you’ve found a leaf node, you’ve found an answer that satisfies the condition, you store that answer, and you end the recursion at this level.

So the termination condition pseudocode of the backtracking function is as follows:

if(Termination condition) {Store result;return;
}
Copy the code

Third, the traversal process of backtracking search (the same as the second step in the previous three recursive steps) was mentioned above, backtracking usually recurses in the set, the size of the set constitutes the width of the tree, and the depth of the recursion constitutes the depth of the tree.

As shown in figure:

Notice that IN this picture, I specifically gave the example that the collection size is equal to the number of children!

The pseudo-code of the backtracking function traversal process is as follows:

for(Select: elements in this layer's collection (the number of children of nodes in the tree is the size of the collection)) {process nodes; Backtracking (path, select list); // undo the result of recursive backtracking}Copy the code

A for loop is a loop that iterates through the set interval, and you can understand that the for loop is executed as many times as the number of children a node has. Backtracking is just calling itself, doing the recursion.

As you can see from the graph, “for loop can be understood as horizontal traversal, backtracking is vertical traversal,” so that the tree is completely traversed. In general, searching for leaf nodes is one of the results.

After analyzing the process, the template framework of backtracking algorithm is as follows:

Void backtracking(parameter) {if(Termination condition) {Store result;return;
    }

    for(Select: elements in this layer's collection (the number of children of nodes in the tree is the size of the collection)) {process nodes; Backtracking (path, select list); // Recursive backtrace, undo result}}Copy the code

“This template is very important, the title of the backtracking method all depends on it!”

If you have never learned the backtracking algorithm, you will be a little confused when you see this, and you will be better off when you start to explain specific problems. If you have done the backtracking problem, you will feel empathy when you see this.

conclusion