《算法笔记》8.1小节——搜索专题-＞深度优先搜索（DFS）问题 A: 【递归入门】全排列

题目描述

排列与组合是常用的数学方法。先给一个正整数 ( 1 < = n < = 10 )，例如n＝3，所有组合,并且按字典序输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1 

输入

输入一个整数n(1<=n<=10)

输出

输出所有全排列，每个全排列一行，相邻两个数用空格隔开（最后一个数后面没有空格。

样例输入

3

样例输出

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

题目链接：Problem A: 【递归入门】全排列 - Codeup新家 

分析：这道题实际上是第4章入门篇（2）——算法初步第3节第2目递归下的例子，当然在第4章也是用递归生成的。实际上用stl的next_permutation()也是可以的。

#include<algorithm>
#include <iostream>
#include  <cstdlib>
#include  <cstring>
#include   <string>
#include   <vector>
#include   <cstdio>
#include    <queue>
#include    <stack>
#include    <ctime>
#include    <cmath>
#include      <map>
#include      <set>
#define ll long long
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
using namespace std;void getans(int n,int index,int *temp,int *flag)
{if(index==n){for(int i=0;i<n;++i)i==0?printf("%d",temp[i]):printf(" %d",temp[i]);printf("\n");}for(int i=1;i<=n;++i){if(flag[i]==0){temp[index]=i;flag[i]=1;getans(n,index+1,temp,flag);flag[i]=0;}}return;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);
//    freopen("in.txt","w",stdout);clock_t start=clock();#endif //testint n;while(~scanf("%d",&n)){int ans[n+5]={0},flag[n+5]={0};getans(n,0,ans,flag);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl;        //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl;    //ms为单位#endif //testreturn 0;
}