算法提高 排列数
时间限制：1.0s 内存限制：256.0MB
问题描述
0、1、2三个数字的全排列有六种，按照字母序排列如下：
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。
012、021、102、120、201、210
输入一个数n
求0~9十个数的全排列中的第n个（第1个为0123456789）。
输入格式
一行，包含一个整数n
输出格式
一行，包含一组10个数字的全排列
样例输入
1
样例输出
0123456789
数据规模和约定
0 < n <= 10!
解题思路：
简单的深度优先，具体内容已写在代码的注释中
1 #include<iostream>
2 using namespace std;
3 #define N 10
4 int a[10],book[10],count,n;//book数组来标记0-9，是否已经使用过 ；a数组存0-9
5 //count 计数(第几个)；n为输入的数
6 void dfs(int step)
7 {
8 int i;
9 if(step==N){//走到底了，也即0-9，满10个数了
10 {
11 count++;//每得到一个结果 自增
12 if(n==count)//找到了结果 输出这一串数
13 {
14 for(i=0;i<N;i++)
15 cout<<a[i];
16 }
17 }
18 return;
19 }
20 for(i=0;i<N;i++)
21 {
22 if(book[i]==0)
23 {
24 a[step]=i;
25 book[i]=1;//标记，i这个数已经使用
26 dfs(step+1);//递归调用
27 book[i]=0;//收回
28 }
29 }
30 return ;
31 }
32 int main()
33 {
34 cin>>n;
35 dfs(0);
36 return 0;
37 }