A SLOW and conventional backtracking version


  • 0
    L

    the idea is very simple. I think no need to explain.

    public int countNumbersWithUniqueDigits(int n) {
            if(n==0) return 1;
            if(n>10) n=10;
            int[] count=new int[11];
            boolean[] visited=new boolean[10];
            for(int i=1;i<=n;i++) backtracking(i,i,count,visited);
            int res=0;
            for(int no:count) res+=no;
            return res;
        }
        public void backtracking(int left,int len, int[] count,boolean[] visited){
            if(left==0) count[len]++;
            if(left>0){
                for(int i=0;i<=9;i++){
                    if((i==0&&left==len)&&len!=1) continue;
                    if(!visited[i]){
                        visited[i]=true;
                        backtracking(left-1,len,count,visited);
                        visited[i]=false;
                    }
                }
            }
        }
    

Log in to reply
 

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