# Furious Teacher

Back Tracking

Medium

#### Problem Statement :

Given `N`, count all the numbers with unique digits less than `10^n`.

See original problem statement here

#### Introduction :

Idea is to traverse all the numbers less than `10^n`, and count the numbers with unique digits with the help of online coding classes. #### Method 1 (Brute-Force):

In this method, we will traverse all the possible numbers. Mark each digit of the number as visited and when any other digit came up which is visited, discard that number. Increment the number count when all the digits of a number are visited and every digit is visited exactly once (No digits are repeated).

#### Method 2 (Backtracking):

Above approach checks all the combinations one after one upto `10^n`. In other words the above approach will iterate upto `10^n` which is beyond the time limit.
In this method we will use backtracking to solve the above problem.

Backtracking is the approach to solve the problem by testing all possible combinations. If any subproblem does not fit the given constraint then we discard the complete subproblem (backtrack), moves a step back then try other remaining possible combinations. Backtracking algorithm is generally exponential in time.
We will store the count of unique digits for each digit (`1-n`).
Now for every digit there are atmost 10 choices (`0-9`). Each time we visit a digit we will mark it as visited so that we wont visit any digit more than once. Now storing the count of individual digits and adding all the counts of individual digits we get our final answer.

#### Back():

1. If `index == target`, increment the count.
2. else, for every `k= 0` to `9` :
• if current digit is not visited, mark it visited and,
• call back(target,index+1,n)
• mark the current digit unvisited (backtracking step).

#### Complexity Analysis :

In the first method we are check all the numbers from `0` to `10^n`. So the time complexity is `10^n`.

## Solutions:

```#include <stdio.h>

int back(int target, int idx, int* visit) {
if (idx == target)
return 1;

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

int solve(int n) {
int visit = {0};
int count = 0;
for (int i = 0; i <= n; i++)
count += back(i, 0, visit);
return count;
}

int main()
{

int n;
scanf("%d",&n);
printf("%d\n",solve(n));

return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

int back(int target, int idx, bool* visit)
{
if (idx == target)
return 1;

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

int solve(int n) {
bool visit = {false};
int count = 0;
for (int i = 0; i <=n; i++)
count += back(i, 0, visit);
return count;
}

int main()
{

int n;
cin>>n;
cout<<solve(n)<<endl;

return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {

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;

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;
}

public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
System.out.println(countNumbersWithUniqueDigits(n));
}
}
```