Java backtracking solution & Iterative solution


  • 1
    B

    Backtracking

    public class Solution {
        int res = 0;
        boolean[] used = new boolean[10];
        public int countNumbersWithUniqueDigits(int n) {
            helper(n, false);
            return res;
        }
        public void helper(int n, boolean includeZero){//the first digit can't be zero, so includeZero is initialized with false
            ++res;
            if(n==0) return;
            for(int i = includeZero? 0: 1;i<=9;++i){
                if(used[i]) continue;
                used[i] = true;
                helper(n-1, true);
                used[i] = false;
            }
        }
    }
    

    Iterative:

    public class Solution {
        public int countNumbersWithUniqueDigits(int n) {
            if(n == 0) return 1;
            int res = 10, tail = 0;
            for(int i = 1;i<n;++i) tail += choose(9, i);
            return res + 9*tail;
        }
        public int choose(int m, int n){// A[m, n]
            int res = 1;
            for(int i = 0;i<n;++i){
                res *= m-i;
            }
            return res;
        }
    }
    

Log in to reply
 

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