AcWing 823. 排列--DFS做法和库函数做法
原题链接
困难
作者:
记_得
,
2021-06-24 23:46:13
,
所有人可见
,
阅读 548
DFS递归做法
#include<iostream>
using namespace std;
int n;
int num[10];
bool st[10];
void dfs(int u)
{
if(u>n)
{
for(int i=1;i<=n;i++) cout << num[i] << ' ';
cout << endl;
}
else
{
for(int i=1;i<=n;i++)
{
if(!st[i])
{
st[i]=true;
num[u]=i;
dfs(u+1);
st[i]=false;
}
}
}
}
int main()
{
cin >> n;
dfs(1);
return 0;
}
用STL下的next_permutation函数,该函数自动帮我们实现了全排列,可以让数组变为比当前排列大的下一个排列,如果当前排列是全排列的最大值时,例如1 2 3全排列,如果当前是3 2 1时,该函数返回值是false,否则为ture。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int n;
cin >> n;
vector<int> res;
for(int i=1;i<=n;i++) res.push_back(i);
do
{
for(int i=0;i<n;i++) cout << res[i] << ' '; //默认就是从最小开始
cout << endl;
} while(next_permutation(res.begin(),res.end()));
return 0;
}