# Two C++ solutions: Backtracking and DP (4 lines only)

• DP solution:

``````class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
vector<int> tbl(min(n,10)+1, 1);
for (int i = 1; i <= min(n,10); i++)
tbl[i] = tbl[i-1] * (i == 1? 9: (9-i+2));
return accumulate(tbl.begin(), tbl.end(), 0);
}
};
``````

Backtracking solution

``````class Solution {
public:
int countNumbersWithUniqueDigits(int n) {
bool visit[10] = {false};
int count = 0;
for (int i = 0; i <= min(10,n); i++)
count += DFS(i, 0, visit);
return count;
}
private:
int DFS(int target, int idx, bool* visit) {
if (idx == target)
return 1;

int count = 0;
for (int i = idx?0:1; i < 10; i++) {
if (!visit[i]) {
visit[i] = true;
count += DFS(target, idx+1, visit);
visit[i] = false;
}
}
return count;
}
};``````

• Can you explain your backtracking method? Thanks

• Can you tell what `min(10,n)` does?

• @anwarshah after 10 digit, there must be one pair of duplicate digit, which can't be counted.

• nice solution!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.