递归实现排列型枚举

前言

传送门 : 94. 递归实现排列型枚举 - AcWing题库

思路

先构思递归搜索树

(看到这就够了)

对于每个节点我们都有 n 种方法

对于每种方法 都有 已经选了 和 没选两种状态

因此考虑一下就是下面这种形式

for(int i=1;i<=n;i++)
{if(!st[i]){p[u] = i;st[i] = 1;dfs(u+1);st[i] = 0;}
}

CODE

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int st[N],n;
int p[N];void dfs(int u)
{if(u == n+1){for(int i=1;i<=n;i++)cout<<p[i]<<" ";cout<<endl;return;}for(int i=1;i<=n;i++){if(!st[i]){p[u] = i;st[i] = 1;dfs(u+1);st[i] = 0;}}}
void solve()
{cin>>n;dfs(1);
}
int main()
{ios::sync_with_stdio(false);solve();return 0;
}