Java Backtracking solution


  • 0

    A similar idea compared with lzb700m in https://discuss.leetcode.com/topic/48001/backtracking-solution. However, I didn't calculate the prev like his solution. Instead, I keep tracking the length of the number.

    public class Solution {
        int count, len;
        public int countNumbersWithUniqueDigits(int n) {
            if (n > 10) return countNumbersWithUniqueDigits(10);
            if (n == 0) return 1;
            len = n;
            count = 1;
            boolean[] visited = new boolean[10];
            for(int i = 1; i < 10; i++){
                // start from 1 to avoid leading zeros
                visited[i] = true;
                helper(1, visited);
                visited[i] = false;
            }
            return count;
        }
        
        private void helper(int step, boolean[] visited){
            count++;
            if (step == len)    return;
            for (int i = 0; i < 10; i++){
                if (visited[i]) continue;
                visited[i] = true;
                helper(step+1, visited);
                visited[i] = false;
            }
        }
    }
    

Log in to reply
 

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