My simple backtracking solution in java


  • 0
    public class Solution {
        int res = 0;
        int step = 0;
        public int countNumbersWithUniqueDigits(int n) {
            if(n == 0) {
                return 1;
            }
            if(n == 1) {
                return 10;
            }
            HashSet<Integer> visit = new HashSet<Integer>();
            helper(0 , (int)Math.pow(10 , n) , n , visit);
            return res + 1; //in backtracking process, we don't add "0".
        }
        
        protected boolean helper(int count , int totalnum , int n , HashSet<Integer> visit) {
            if(count >= n) {
                return false;
            }
            if(step == totalnum) {
                return true;
            }
            for(int i = 0 ; i <= 9 ; i++) {
                step++;
                if((count == 0 && i == 0) || visit.contains(i)) {
                    continue;
                }
                res++;
                visit.add(i);
                if(helper(count+1 , totalnum , n , visit)) {
                    return true;
                }
                visit.remove(i);
            }
            return false;
        }
    }

Log in to reply
 

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