Super Simple DFS Java/C# solution


  • 0
    X
    public class Solution
        {
            public int CountNumbersWithUniqueDigits(int n)
            {
                return CountNumbersWithUniqueDigitsHelper(n, 0) + 1;
            }
    
            public int CountNumbersWithUniqueDigitsHelper(int n, int currentNumDigits)
            {
                if(currentNumDigits == n) return 0;
                    
                int sum = 0;
                for (int i = currentNumDigits; i < (currentNumDigits == 0 ? 9 : 10); i++)
                {
                    sum += 1 + CountNumbersWithUniqueDigitsHelper(n, currentNumDigits + 1);
                }
                return sum;
            }
        }
    

    Every node of the DFS forms a number and when you go one level deeper you have one less digit to use. The first recursion call has a trick that you only should use 9 digits instead of 10. That's because the numbers starting with 0 will already be covered in other nodes. i.e: 01,02,03,04... etc is already covered by the call to 1,2,3,4... The only number missing will be the actual 0, that's why the final +1 sum on the recursion call.


Log in to reply
 

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