An example of recursion, the full permutation problem of 1~n

Yes 1-n Make a full arrangement , The idea is as follows ：

Set the current arrangement order as P, For the next digit to be filled index, Traverse in turn 1-n Judge x Whether in The current arrangement P in , If not (hashtable[x] = false), Then add it to P Of index Location (P[index] = x, hashtable[x] = true), Then enter the next function to fill in the next position ; At the end of traversal , The current position to be filled is n + 1, At this point, the output sequence is traversed P that will do ; After this round, you will index Take out the number at (hashtable[x] = flase);

To sum up, we can get ： Recursive boundary is index = n + 1 At this point, print the sequence P, Recursive equations （ The process ） Is not added to P The numbers in the sequence are placed on the index It's about , Then fill in index + 1 The number of places , Take out the number after finishing the arrangement , Prepare for the next sort

A recursive process ： With 1~3 For example, the full permutation of n = 3

1. index = 1： First fill in the first position , The filling position is index = 1, perform else part ; Traverse the sort sequence 1~n Find unfilled elements , First find 1 Not filled , take 1 Put in P[1],hashtable[1] Set up true, Fill in the position 1 after , Recursively fill in the next position 2, namely index + 1;
2. index = 2：index != n + 1; perform else; loop x = 1, Already in the sequence , Do not fill in , Loop to x = 2, fill p[2], Go to the next function ;
3. index = 3：index != n + 1; perform else; loop x = 1, Already in the sequence , Do not fill in , Loop to x = 3, fill P[3], Go to the next function ;
4. index = 4：index == n + 1; Ergodic input P The sequence is 123;
5. After executing this function, return to the previous layer ,index = 3, Execute the next statement , About to fill in P[3] Take out the elements of , Here will be 3 Take out , because for Loop to x = 3, So the cycle is over , Back to the next level ;
6. index = 2： This layer pair 2 Fill in , Execute the next statement , About to fill in P[2] Take out the elements of , Here will be 2 Take out , because for Loop to x = 2, So execute the next loop x = 3, In this cycle 3 Not in the sequence , So put P[2], Go to the next function ;
7. index = 3： Re enter this layer to execute else part , Traversal found 2 Not filled , So it will 2 fill , the 2 Put in P[3], Go to the next function ;
8. index = 4： Traverse the output P The sequence is 132;
9. ……

#include<cstdio>
const int maxn = 11;
int n, P[maxn];
bool hashtable[maxn] = {
    false};
void full(int index) {
    
	if(index == n + 1) {
    
		for(int i = 1; i <= n; i++) {
    
			printf("%d", P[i]);
		}
		printf("\n");
	} else {
    
		for(int x = 1; x <= n; x++) {
    
			if(hashtable[x] == false) {
    
				P[index] = x;
				hashtable[x] = true;
				full(index + 1);
				hashtable[x] = false;
			}
		}
	}
} 
int main() {
    
	n = 3;
	full(1);
	return 0;
}

123
132
213
231
312
321