XTUOJ-1270 Unique Digit Number

数位不同的数

题目描述

数位不同的数是指所有数位上的数码都不一样的数，比如“123”三个数码1,2,3，都不一样，所以是数位不同的数；但是“1232”中有两个相同的数码2，所以不是。请写一个程序，计算第几个符合条件的数是什么？

输入

每行输入一个整数n(1≤n≤8877691)。

输出

每行输出一个整数，为对应样例的结果。

样例输入

1
10
100
8877691

样例输出

0
9
120
9876543210

思路

我就一蒟蒻，只能搞搞暴搜了，希望有位大佬能教我递推。

每位数字不同，自然而然地想到了全排列，然后保存答案即可。

不过由于题目 0 ~ 9 都要，就不是一般的全排列了，判断得一直到10为止。

一共有10位，从第 1 位开始，到第 10 位全都扫一遍。

void dfs(__int64 x, int n, int wei){
    if(n == wei){// 等到位数相同
        ans[++top] = x;// 不赶紧储存愣着干嘛
    }else{
        for(int i = 0; i < 10; i++){// 1 ~ 9，一个都不能少
            if(is[i])// 当前数用过了
                continue;
            if(x || i){// 排除 0
                is[i] = true;// 标记
                dfs(x * 10 + i, n + 1, wei);// 找下一位数
                is[i] = false;// 回溯
            }
        }
    }
}

cin 搞得我差点超时