**Solution**

**Count Numbers with Unique Digits** https://leetcode.com/problems/count-numbers-with-unique-digits/?tab=Description

**Brute Force**

- Brute force will be to generate each number and test whether it has unique digits or not.
- Boundary Condition: What happens when n is more than 10? Unique numbers are limited to the case of n = 10.
- Split the problem in this view. Say N = 4. 0<=x<=9999.
- This means that: [0, 1 to 9, 10 to 99, 100 to 999, 1000 to 9999].
- Now implement backtracking for each of these ranges and keep adding to count.

```
class Solution(object):
def helper(self, i, dedup, n):
if i == n:
return 1
else:
count = 0
start = 1 if i == 0 else 0
for x in range(start,10):
if x not in dedup:
dedup.add(x)
count = count + self.helper(i+1, dedup, n)
dedup.remove(x)
return count
def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
count = 0
for j in range(0, n+1):
count = count + self.helper(0, set([]), j)
return count
```

**Dynamic Programming**

- Next you can improve backtracking by dynamic programming. Assume you want to know all unique digit numbers from 100 to 999. First place can take 9 (1 to 9). Second place can take 9 (0 to 9 but not what we took in first place). Last place can take only 8.

https://goo.gl/photos/oLz3dmPimXBgWWsDA

Example: n=4

- n = 1 temp = 9
- n = 2 temp = 9 * 9
- n=3 temp = 9 * 9 * 8
- n=4 temp = 9 * 9 * 8 * 7

```
class Solution(object):
def countNumbersWithUniqueDigits(self, n):
"""
:type n: int
:rtype: int
"""
soln, temp, factor = 1, 1, 9
for i in range(n):
temp = temp * factor
soln = soln + temp
factor = factor-1 if i!=0 else factor
return soln
```