LeetCode: Count Numbers with Unique Digits

Count Numbers with Unique Digits

양수인 n 이 주어 졌을때 \(10^n\) 보다 작고 0보다 크거나 같은
모든 숫자가 unique 한 숫자의 갯수를 리턴해라
예 n = 2, return 91. 11, 22, 33, 44, 55, 66, 77, 88, 99 는 같은 숫자를 가지고 있으니 100 - 9 = 91.
예 n = 3, return 739
수학 문제인데요.
여기서 알아야 할 것은 n = 1 일때는 10 0 ~ 9 인 걸 알고
n = 2 일때 부터 겹치는게 생기는 걸 알 수 있습니다.
이걸 어떻게 생각하면 될까요? n = 2 때 생각을 해보죠
n = 1 일때 0 - 9 까지 가능했는데 십의 자리에 1-9를 넣을 수 있습니다. 그럼 10 - 99 까지 만 들 수 있죠?
하지만 n = 1 일때 숫자가 1-9 까지 9개가 겹 칠 수 있습니다. 따라서 9 * 10 - 9 가 10~99 까지의 unique 한 갯수죠.
n = 3 일 때 볼까요?
0~99 까지 저희는 91개가 있다는걸 알죠. 그럼 그냥 100의 자리에 1-9 를 넣으면 되죠.
총 9 * 91 개를 만 들 수 있죠. 하지만 12, 13 이런 숫자를 볼까요? 12는 112 212 가 불가능 합니다. 겹치는 숫자가 나오니까요.
13 은 113 과 313 이 불가능 하죠. 2자리 수들은 그럼 2 * (10 ~ 99 unique 갯수 만큼) 빼줘야 겠군요. 1, 2, 3 이런 숫자들은 어떨까요? 101, 202 이런 숫자들이 안되는걸 알 수 있죠. 그럼 1 * (1 ~ 9 의 unique 갯수) 를 빼주면 되겠네요.
n = 4 일때 한 번 해보시기 바랍니다. 보면 n = 2 은 (그 전 합) + 9 * (안 겹쳤던 수) - 겹치는 수 = 10 (n = 1) + 9 * 10 - 9 = 91
n = 3 은 91 (n = 1 ~ 2) + 91 * 9 - 2 * 81 (n = 2) - 1 * 9 = 739
n = 4 은 739 (n = 1 ~ 3) + 739 * 9 - 3 * 648 - 2 * 81 - 1 * 9 = 5275

public int countNumbersWithUniqueDigits(int n) {
    if (n == 0) return 1;
    int curSum = 10; // current sum 
    int prev = 9; // prev n's sum
    int totalSub = 0; // total subtract until now
    for (int i = 2; i <= n; ++i) {
        // 9 * (curSum) - (totalSub) - (i - 1) * prev (unique digits beteen n's digits) (n = 2 => 10 - 99)
        int tmp = curSum;
        curSum = curSum * 9 - totalSub - (i - 1) * prev;
        totalSub += (i - 1) * prev;
        prev = curSum;
        curSum += tmp;
    }
    return curSum;
}