This is the 9th day of my participation in the August More Text Challenge. For details, see:August is more challenging

If you want to keep writing, write a series. What can I write about? Program = algorithm + data structure, which shows the importance of algorithm. This series of old poems tries to explain the algorithm clearly in the simplest language, from shallow to deep, if you are interested, you can pay attention to the column.

I’ve written sorting algorithms, basic operations and high-end operations for linked lists. Now let’s talk about backtracking. This is actually an entry-level algorithm in the algorithm competition class. Although it is an entry-level algorithm, but you do not say, there are still a lot of people will not.

Let’s do a full permutation with the algorithm today: enter n, for example n=3 123 132 213 231 312 321

What we’re going to do is print out the full array of 3 on the screen.

Now, this looks like a very simple problem, but if you haven’t studied the algorithm, you might not be able to do it. At first glance, it could be done with cyclic violence. If n is fixed at 3, then you can do a three-tier loop and you solve the problem for(I =1; i<=3; i++) … for(j=1; j<=3; j++) … for(k=1; k<=3; k++) …

And then here… Is to do pruning operation, what is pruning? Here’s an extension. That’s the constraint. Pick out the things that don’t satisfy. Obviously, our part-time offer is I! =j ,i! =k,j! = k. In other words, iJK cannot be equal to each other. See how you can do this if n is fixed at 3.

But n is not fixed, we could be 4, we could be 5, we could be 100. So there’s no way we can write a loop of uncertain levels. So we need recursion here. That is to call itself..

The complete code is as follows:

#include<iostream> using namespace std; int n,a[100],isUse[100]; Void DFS (int index) {if(index>n)// if(index>n)// if(index>n)// if(index>n)// if(index>n)// if(index>n)// if(index>n); {.. Cout <<a[I]<<" "; } cout<<endl; return; } for(int i=1; i<=n; i++) { if(! IsUse [I]) {DFS (index+1); isUse[i]=0; // When you go back, you must clearly mark it, otherwise the next permutation can be selected. This is the most important point, think about it carefully. } } } int main() { while(cin>>n) { dfs(1); }}Copy the code

Don’t underestimate this algorithm, it can be used in many situations. If you are interested, you can do the following:

Problem, you can pay attention to the public number: poetic code

Now that I’m in, it’s not easy to be original. Let’s go with a “like”.