1.3.1 Full Permutation Problem

1.3.1 The total permutation problem

Description

Output natural numbers 111 To nnn All the non repetitive permutations , namely nnn The whole arrangement , It is required that no duplicate number is allowed in any number sequence generated .

Input

The first line is an integer nnn

Output

from 111 to nnn A sequence of all the numbers that do not repeat , One sequence per line .

Each number is separated by a space

Sample Input 1

3

Sample Output 1

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Hint

1≤n≤91 \le n \le 91≤n≤9

#include<stdio.h>//uncle-lu
/*
 Perform a depth first search on the current location , Find each number you can fill in and try . After searching this location, go back and continue searching .
*/
int n;
int line[10];
bool visit[10];
void print()
{
	for(int i=1; i<=n; ++i)
		printf("%d ", line[i]);
	printf("\n");
	return ;
}
void dfs(int x)
{
	if(x>n)
	{
        print();//objective 4 altogether n After searching all the numbers, what should we do ？
	}
	for(int i=1; i<=n; ++i)
	{
		if(visit[i])  continue;//objective 1  What if this number is used ？
		else
        {
            line[x]=i,visit[i]=1;//objective 2 If not used, search this number , What needs to be handled ？ In order not to repeat how we should use visit Array tags ？
            dfs(x+1);
            visit[i]=0;
        }
	}
	return;
}

int main()
{
	scanf("%d",&n);
	dfs(1);//objective 3 Where should we search first ？
	return 0;
}