题意 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ > 按照字典序输出自然数 111 到 nnn 所有不重复的排列，即 nnn的全排列，要求所产生的任一数字序列中不允许出现重复的数字。 题目要求我们输出的是nnn的全排列，而不是组合(组合与排列的区别) 所以我们可以利用深度优先搜索的特性(DFS)，来解决这道题目 * 首先我们已知的样例如下： 即在DFS中每达到一次规定的数字数量，输出，同时保证不重复。 相当于套个DFS的模板。 注意：输出时：每个数字保留 555 个场宽。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ AC CODE: * 结语：此题为模板题，如果还是不太理解，建议重新学习DFS板块！

以4 2 5 3 1为例： 1.从后往前，找到第一个前面的数小于后面的数.这里是2. 2.从后往前，找到第一个比当前数大的数.这个数是3. 3.交换这两个数. 4.在3后面的数用升序排列（由于后面的数已是降序，可以使用反转节省时间）. 进行完操作后的数列为4 3 1 2 5.

nextpermutationnext_permutationnextp ermutation真的太好用了

#include<iostream> using namespace std; int n; int a[100001]; bool flag[100001]={0}; void dfs(int step) { if(step>n) { for(int i=1;i<=n;i++) { cout<<" "<<a[i]; } cout<<endl; } for(int i=1;i<=n;i++) { if(flag[i]==0) { a[step]=i; flag[i]=1; dfs(step+1); flag[i]=0; } } } int main() { cin>>n; dfs(1); return 0; }

Sβ

#include<bits/stdc++.h> using namespace std; int n,a[13],book[13]; void dfs(int x) { if(x>n) { for(int i=1;i<=n;i++) cout<<" "<<a[i]; cout<<endl; return; } for(int i=1;i<=n;i++) { if(book[i]==0) { book[i]=1; a[x]=i; dfs(x+1); a[x]=0; book[i]=0; } } } int main() { cin>>n; dfs(1); }

直接模板化，超简单的全排列，最难的反而是格式化控制......