AcWing 842. 排列数字

AcWing 842. 排列数字

dfs就是一个递归的过程 n=4时的 过程推理 n=4的过程分析： dfs内嵌dfs

对于 第一层for()也就是 i=1的时候 第一层dfs(1）第二层 for （）i=2 第二层dfs(2)的时候 a[0]=1;a[1]=2;st[1]=1;st[2]=1;

最内层的DFS 因为前面几层的标记 （st[i]=1）最后只有一个数字4符合 倒数第二层 同理 有2个数字 因为for循环 倒数第二个数会依次扫到 3 4 然后依次调用2次 最后结果 是 1234 1243 也就是 最后两个数的全排列 对于 1-2层 for循环同理 3个数的全排列–>四个数的 全排列

#include<map> #include<set> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<sstream> #include<algorithm> using namespace std; #define ll long long #define mem(a,b) memset((a),(b),sizeof(a)); #define lowbit(a) ((a)&-(a)) const ll inf=0x3f3f3f3f;//1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); const int N=1e3+10; int a[100]; bool st[100]; int n; void dfs(int x){ if(x==n){ for(int i=0;i<n;i++){ cout<<a[i]<<" "; } cout<<endl; return ; } for(int i=1;i<=n;i++){ if(!st[i]){ a[x]=i; st[i]=1; dfs(x+1); st[i]=0; } } } int main(){ //#define io #ifdef io freopen("in.txt","r",stdin); #endif cin.tie(0); cin>>n; dfs(0); return 0; }