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])

Solution 1: When n == 0, return 1.

When n == 1, _ can put 10 digit in the only position. [0, ... , 10]. Answer is 10.

When n == 2, _ _ first digit has 9 choices [1, ..., 9], second one has 9 choices excluding the already chosen one. So totally 9 * 9 = 81. answer should be 10 + 81 = 91

When n == 3, _ _ _ total choice is 9 * 9 * 8 = 684. answer is 10 + 81 + 648 = 739

When n == 4, _ _ _ _ total choice is 9 * 9 * 8 * 7.

...

When n == 10, _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

When n == 11, _ _ _ _ _ _ _ _ _ _ _ total choice is 9 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1 * 0 = 0

    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        int ans = 10, uniqueDigits = 9, availableDigits = 9;
        while (n > 1 && availableDigits > 0) {
            uniqueDigits *= availableDigits;
            ans += uniqueDigits;
            availableDigits--;
            n--;
        }
        return ans;
    }

Solution 2: backtracking

    public int countNumbersWithUniqueDigits(int n) {
        return doCount(n, new boolean[10], 0);
    }
                                              //d-th place starting from 0
    private int doCount(int n, boolean[] used, int d) {
        if (d == n) return 1;
        int total = 1;
        //第一位(d==0)不能为0
        for (int i = (d == 0) ? 1 : 0; i <= 9; i++) {
            if (!used[i]) {
                used[i] = true;
                total += doCount(n, used, d + 1);
                used[i] = false;
            }
        }
        return total;
    }