背景

本题求的是1-n的全排列，emm我也不知道为啥会放在新手村，因为这道题需要用到dfs算法。还不知道dfs的同学可以康康这个 https://blog.csdn.net/qq_51536841/article/details/120892489?spm=1001.2014.3001.5501 明白了dfs就很好做了

思路

就是分别把每个数字放在每个位置上，比如n==3时，第一个位置先放1，然后把1标记已经使用，第二个位置就只能放2或3，如果放2，再把2标记，那么第三个位置就只能放3，然后返回第二个位置放3，把2的标记去掉，那么第三个位置就只能放2，再返回到第一个位置，第一个位置放2，把1的标记取消，就可以在后面的位置放1，以此类推。

附上代码

#include<iostream>
using namespace std;
#define N 10000
int a[N]; 
int pd[N]={0};
int n;
void print(){
for(int i=1;i<=n;i++){
	printf("%d ",a[i]);
}cout<<"\n";
} 
void dfs(int x){
if(x==n){
	print();//x表示的是当前已经放了几个数了，当n个的时候就可以输出了
	return;
}
for(int i=1;i<=n;i++){
	if(!pd[i]){/i未被标记，即可使用
		a[x+1]=i;//讲i放再a数组里
		pd[i]=1;//标记i表示i被放过了
		dfs(x+1);//然后dfs下一个
		a[x+1]=0;//此时已经返回当前这个位置了，就表示这个数已经用过了，要换下一个排列了
		pd[i]=0;//标记取消让笑一个位置可以用这个数。
	}
}
}
int main(){
cin>>n;
dfs(0);
return 0;
}

1.递归调用（dfs）：

#include<bits/stdc++.h>
using namespace std;

void permutation(vector<int> a, int begin_, int end_){
    if(begin_ == end_){
        for(auto i:a)cout<<i<<" ";
        cout<<endl;
        return;
    }
    for(int i=begin_;i<=end_;i++){
        swap(a[i],a[begin_]);
        sort(a.begin()+begin_+1,a.begin()+end_+1);
        permutation(a, begin_+1, end_);
        swap(a[i],a[begin_]);
    }
}

int main(){
	int n;
	cin>>n;
	vector<int> a;
	for(int i=1;i<=n;i++){
		a.push_back(i);
	}
	sort(a.begin(),a.end());
    permutation(a, 0, n-1); //传入的数组，起始下标
	
	return 0;
}

2、stl库中的next_permutation函数：

#include<bits/stdc++.h>
using namespace std;

int main(){
int n;
cin>>n;
vector<int> a;
for(int i=1;i<=n;i++){
a.push_back(i);
}
sort(a.begin(),a.end());

do
{
for(auto i:a)cout<<i<<" ";
cout<<endl;
} while(next_permutation(a.begin(),a.end()));

return 0;

}

除了用dfs解决这个问题以外，我们也可以用一用stl库里面的next_permutation

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

int num[10000005];

int main(void)
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) num[i-1]=i;
	sort(num,num+n);
	
	do{
		for(int i=0;i<n;i++) cout<<num[i]<<" ";
		cout<<endl;
	}while(next_permutation(num,num+n));
	
	
	
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
int a[N];
bitset<N> vis;
int n;
void dfs(int deep1)
{
    if(deep1 == n+1) 
    {
        for(int i = 1;i <= n;i++)cout<<a[i]<<" ";
        cout<<"\n";
        return;
    }
    //vis[deep1] = true;
    for(int i = 1;i <= n;i++)
    {
        if(vis[i]) continue;
        vis[i] = true;
        a[deep1] = i;
        dfs(deep1+1);

        a[deep1] = 0;
        vis[i] = false;

    }
}
int main()
{
    //int n;
    cin>>n;
    dfs(1);
    
    return 0;
}