Count Numbers with Unique Digits

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < $$10^n$$.

Example: Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding [11,22,33,44,55,66,77,88,99])

题目大意是：给定n，求出所有小于$$10^n$$的所有的数(数中的数字唯一），显然这个可以用排列组合来解

1位数 (0，1, 2, 3, 4, ...9)中选一个 是10；

2位数 最高为不能为0，所以是 9*9 = 81;

3位数 998

...

9位数 998765432;

10位数 998765432*1；

11位数 0；

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n == 0)  return 1;

        int high = 9;
        int rem = 9;

        int res = 10;

        while(n--> 1 && rem > 0){
            high = high * rem;
            res += high;
            rem--;
        }

        return res;
    }
};

回溯法:会超时

class Solution {
public:
    int countNumbersWithUniqueDigits(int n) {
        if(n > 10)  return countNumbersWithUniqueDigits(10);

        vector<int> used(10, 0);

        long max = (long)pow(10, n);

        //n == 0
        int count  = 1;

        for(int i = 1; i < 10; ++i){
            used[i] = 1;
            count += dfs(i, max, used);
            used[i] = 0;
        }
        return count;
    }
private:
    int dfs(long prev, long max, vector<int> used){
        int count = 0;
        if (prev < max) {
            count += 1;
        } else {
            return count;
        }

        for (int i = 0; i < 10; i++) {
            if (!used[i]) {
                used[i] = 1;
                long cur = 10 * prev + i;
                count += dfs(cur, max, used);
                used[i] = 0;
            }
        }

        return count;
    }
};