# Backtracking solution

• The idea is to append one digit at a time recursively (only append digits that has not been appended before). Number zero is a special case, because we don't want to deal with the leading zero, so it is counted separately at the beginning of the program. The running time for this program is O(10!) worst case, or O(n!) if n < 10.

The OJ gives wrong answer when n = 0 and n = 1. The correct answer should be:

0, 1

1, 10

2, 91

3, 739

4, 5275

5, 32491

6, 168571

7, 712891

8, 2345851

9, 5611771

10 and beyond, 8877691

``````public class Solution {
public static int countNumbersWithUniqueDigits(int n) {
if (n > 10) {
return countNumbersWithUniqueDigits(10);
}
int count = 1; // x == 0
long max = (long) Math.pow(10, n);

boolean[] used = new boolean[10];

for (int i = 1; i < 10; i++) {
used[i] = true;
count += search(i, max, used);
used[i] = false;
}

return count;
}

private static int search(long prev, long max, boolean[] used) {
int count = 0;
if (prev < max) {
count += 1;
} else {
return count;
}

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

return count;
}
}``````

• modify ‘prev <= max’ to 'prev<max' as 0 ≤ x < 10^n

• Thanks.

They have just modified the problem description. Before it was 0 ≤ x ≤ 10^n.

• I like your solution because it's much easier to understand than those math tricks.

• good Backtrack solution.

• When n > 10, it should be 0 based on Pigeonhole principle

• you only considered the number between 10^10 and above, but you also need to include the number from 0 to 10^10.

• You are right!

• ``````public class Solution {
public static int countNumbersWithUniqueDigits(int n) {
}

public static int countNoneRepeat(int n, HashSet<Integer> alreadyHave) {
if (n < 1) {
return 1;
}

int result = 0;
for (int i = 0; i < 10; i++) {
} else {
if (i == 0 && alreadyHave.size() == 1) {
}
}
}
return result;
}
}``````

• It would be better if we change the following

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

with

`````` for(int i=0;i<10;i++){
if(!used[i]){
used[i]=true;
long cur = 10 * prev + i;
int tmp=search(cur, max, used);
used[i]=false;
if(tmp==0)
break;
count+=tmp;
}
}
``````

• could you explain this part?
if (i == 0 && alreadyHave.size() == 1) {
}

• very nice and neat solution, here is some improvement in my point of view. I add a depth variable so that there is no need to write down the for loop outside the recursion.
Code like this

`````` public static int countNumbersWithUniqueDigits(int n) {
int count=0;
if (n==0)
return 1;
int max= (int)Math.pow(10,n);

boolean used[] = new boolean[10];
count+=dfs(0,max,used,0);
return count;

}
public static int dfs(int prev,int max,boolean[] used,int depth){
int count=0;
if(prev>=max){
return count;
}
count++;
for(int i=0;i<10;i++){
if(depth==0 && i==0)
continue;
if(!used[i]) {
used[i]=true;
int nownum = prev * 10 + i;
count+=dfs(nownum,max,used,depth+1);
used[i]=false;
}
}
return count;
}
``````

• @futurehau if you do like this, it will be wrong.

• My simplified version by counting digits left, easier to understand than OP's version.

``````public class Solution {
public int countNumbersWithUniqueDigits(int n) {
int count = 0;
if (n == 0) return 1;
boolean[] flags = new boolean[10];
count += countNumbersWithUniqueDigits(n-1);
for (int i = 1; i < 10; i++) {
flags[i] = true;
count += search(n-1, flags);
flags[i] = false;
}
return count;
}

public int search(int n, boolean[] flags) {
if (n == 0) {
return 1;
}
int count = 0;
for (int i = 0; i < 10; i++) {
if (flags[i] == false) {
flags[i] = true;
count += search(n-1, flags);
flags[i] = false;
}
}
return count;
}
}
``````

• Thank you so much for the backtracking solution. I actually like this kind of normal solution more than Math solution.

Here is my code, using bitmask, as Show Hint said.

``````public class Solution {
public int countNumbersWithUniqueDigits(int n) {
if (n > 10) return countNumbersWithUniqueDigits(10);
long max = (long)Math.pow(10, n);
int used = 0;
int count = 1; // 0
for (int i = 1; i < 10; i++) {
used ^= (1 << i);
count += helper(i, max, used);
used ^= (1 << i);
}
return count;
}

private int helper(long pre, long max, int used) {
int count = 0;
if (pre < max) {
count++;
} else {
return count;
}

for (int i = 0; i < 10; i++) {
if ((used >>> i & 1) == 1) continue;
used ^= (1 << i);
long cur = 10 * pre + i;
count += helper(cur, max, used);
used ^= (1 << i);
}
return count;
}
}
``````

• Hi guys, can anyone have a look for my python codes? I think I use the very similar way like this post, but my codes always exceed the time limit. Thank you, guys, my codes is below:
'''

class Solution(object):

``````def countNumbersWithUniqueDigits(self, n):
if n==0:
return 1
elif n==1:
return 10
else:
count=[10]
for i in range(1,10):
self.backtracking(i,10**n,[False]*i+[True]+[False]*(9-i),count)
return count[0]

def backtracking(self,current,limit,visited,count):
for i in range(0,len(visited)):
if not visited[i]:
if current*10+i<limit:
count[0]+=1
self.backtracking(current*10+i,limit,visited[:i]+[True]+visited[i+1:],count)
``````

'''

• Not so understandable

• Translate to Python, but got TLE

``````class Solution(object):
def backtrack(self, prev, max_val, used):
count = 0
if prev < max_val:
count += 1
else:
return count
for i in xrange(10):
if not used[i]:
used[i] = True
cur = 10 * prev + i
count += self.backtrack(cur, max_val, used)
used[i] = False
return count

def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
if n > 10:
n = 10
max_val = 10 ** n
used = [False] * 10
count = 1
for i in xrange(1, 10):
if not used[i]:
used[i] = True
count += self.backtrack(i, max_val, used)
used[i] = False
return count
``````

Two accept variations based on the same idea, each takes 2100+ ms

``````class Solution(object):
def backtrack(self, used, n, cur):
if cur == 0:
return 1
count = 0
for i in xrange(10):
# ignore leading zero cases, because we count them separately
if cur == n and i == 1:
continue
if not used[i]:
used[i] = True
count += self.backtrack(used, n, cur - 1)
used[i] = False
return count

def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
used = [False] * 10
count = 0
# count n = 0, 1, 2, ..., separately
for j in xrange(n + 1):
count += self.backtrack(used, j, j)
return count
``````
``````class Solution(object):
def backtrack(self, used, n, cur):
if cur == 0:
return 1
# initialize count with 1, it will remedy ignored leading zero cases, but I actually don't understand why this works
count = 1
for i in xrange(10):
if n == cur and i == 0:
continue
if not used[i]:
used[i] = True
count += self.backtrack(used, n, cur - 1)
used[i] = False
return count

def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
used = [False] * 10
return self.backtrack(used, n, n)
``````

• said in Backtracking solution:

because we don't want to deal with the leading zero, so it is counted separately at the beginning of the program.

I'm not sure where does this code count the leading zero case?

• @xiangxy
In my opinion:
the first for loop within the countNumbersWithUniqueDigits, starting from 1, end at 9. Without considering the leading 0 case. That's why we need a max value in the search method to act as "loop stopper" in the search method.

``````        if (prev < max) count++;
else return count;   //reach max, return
``````

Jump to search method, The first "prev" only consider 1-9, and the first i in the search method is 0, then we call the search again, the current value become 10*prev(10,20,30....90) + i(Now the i could be 0~9) .

Hope it helps.

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