共计 674 个字符，预计需要花费 2 分钟才能阅读完成。
题目地址：https://leetcode-cn.com/probl… 题目描述：给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10 的 n 次方。
示例:
输入: 2 输出: 91 解释: 答案应为除去 11,22,33,44,55,66,77,88,99 外，在 [0,100) 区间内的所有数字。即这个数最多 n 位。
解答：这一题就是利用回溯法求组合数，从 (0,1,2,3,4,5,6,7,8,9) 这个集合中求 c(k,1)+…+c(k,k),k>=1,k<=n。求组合的代码很好写，需要注意的是第 1 为不能为 0, 所以不能从第 1 位开始调用，而是要从第 2 位开始（下面的 backtrack(1,k,flag); 这里的 1 就是第二位，因为从 0 开始算位数）。java ac 代码:
class Solution {
int ans;
public int countNumbersWithUniqueDigits(int n) {
boolean[]flag = new boolean[10];
for(int k = 1;k <= n;k++)
for(int j = 1; j <= 9;j++){
flag[j] = true;
backtrack(1,k,flag);
flag[j] = false;
}
return ans+1;
}
void backtrack(int i,int n,boolean[]flag)
{
if(i == n)
{
ans++;
return;
}
for(int j = 0;j <= 9;j++)
if(!flag[j])
{
flag[j] = true;
backtrack(i+1,n,flag);
flag[j] = false;
}
}
}
