Backtracking solution


  • 27
    L

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

  • 0
    H

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


  • 1
    L

    Thanks.

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


  • 1
    V

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


  • 0
    J

    good Backtrack solution.


  • 0
    A

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


  • 0
    L

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


  • 0
    A

    You are right!


  • 0
    S
    public class Solution {
        public static int countNumbersWithUniqueDigits(int n) {
            HashSet<Integer> alreadyHave = new HashSet<>();
            return countNoneRepeat(n,alreadyHave);
        }
    
        public static int countNoneRepeat(int n, HashSet<Integer> alreadyHave) {
            if (n < 1) {
                return 1;
            }
    
            int result = 0;
            for (int i = 0; i < 10; i++) {
                if (!alreadyHave.contains(i)) {
                    alreadyHave.add(i);
                    result += countNoneRepeat(n-1,alreadyHave);
                    alreadyHave.remove(i);
                } else {
                    if (i == 0 && alreadyHave.size() == 1) {
                        alreadyHave.remove(0);
                        result += countNoneRepeat(n-1,alreadyHave);
                    }
                }
            }
            return result;
        }
    }

  • 1
    F

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

  • 0
    S

    could you explain this part?
    if (i == 0 && alreadyHave.size() == 1) {
    alreadyHave.remove(0);
    result += countNoneRepeat(n-1,alreadyHave);
    }


  • -1
    K

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

  • 0

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


  • 2
    M

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

  • 0

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

  • 0
    G

    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)
    

    '''


  • 0

    Not so understandable


  • 0
    N

    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):
                # ignore leading zero cases
                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)
    

  • 0
    X

    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?


  • 0

    @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.


Log in to reply
 

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