【回溯-数字全排列&&dfs】leet 357. 统计各位数字都不同的数字个数

给你一个整数 n ，统计并返回各位数字都不同的数字 x 的个数，其中 0 <= x < 10n。示例 1：

输入：n = 2
输出：91
解释：答案应为除去 11、22、33、44、55、66、77、88、99 外，在 0 ≤ x < 100 范围内的所有数字。 

示例 2：

输入：n = 0
输出：1

提示：

• 0 <= n <= 8

其实就是统计长度为n，由【0，9】的数字构成的字符串的全排列个数，但是000这种也算是合理的数字。所以和全排列又有不同。

在选择数字的时候允许出现前缀0.

static class Solution {
    public int count=0;
    public int countNumbersWithUniqueDigits(int n) {
        dfs(0,n,new boolean[10],0);
        return count;
    }

    public void dfs(int i,int n,boolean[] u,int v){
        if(i==n){
            count++;
            return;
        }
        for(int d=0;d<=9;d++){
            if(v!=0&&u[d]) continue;  
			//如果不是前缀0，并且d在前面出现过，不被允许。如果是前缀0，则d可以随意选择
            u[d] = true;
            dfs(i+1,n,u,v*10+d);
            u[d]=false;
        }
    }

}

}