ADV-188 算法提高 排列数
问题描述
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!
解题思路：使用dfs来解排列数的题
直接上代码：
public class Main {
static int a[] = new int[11];//存数
static int book[] = new int[11];//标记数组
static final int value = 10;
static int n = 0;
static int count = 0;//计数，与n比较
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
n = s.nextInt();
dfs(0);
}
private static void dfs(int step) {
if (step == value) { //排列0--9十个数，step从0加到9，当step==10说明排列完成
count++;
if (count == n) {
for (int i = 0; i < value; i++)
System.out.print(a[i]);
}
}
for (int i = 0; i < value; i++) {
if (book[i] == 0) {
a[step] = i;
book[i] = 1;
dfs(step + 1);
book[i] = 0;//标记完后要释放
}
}
}
}