357.Count Numbers with Unique Digits

Tags: [recursion], [backtracking]

Link: https://leetcode.com/problems/count-numbers-with-unique-digits/\#/description

Given a non-negative integer n, count all numbers with unique digits, x, where 0 ≤ x < 10n.

Example:
Given n = 2, return 91. (The answer should be the total numbers in the range of 0 ≤ x < 100, excluding[11,22,33,44,55,66,77,88,99])

Solution: Backtracking

class Solution(object):
    def __init__(self):
        self.counter = 0

    def countNumbersWithUniqueDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 0:
            raise ValueError('The input is invalid')
        if n == 0:
            return 1

        digit_set = set()
        self.build_nums(n, digit_set)
        return self.counter

    def build_nums(self, n, digit_set):
        # base case
        if len(digit_set) == n:
            return

        for digit in xrange(9 + 1):
            if digit in digit_set or (len(digit_set) == 1 and (0 in digit_set)):
                continue

            digit_set.add(digit)

            self.counter += 1
            self.build_nums(n, digit_set)

            digit_set.remove(digit)

Revelation:

• Be careful of the leading 0, cannot build the numbers such as, 01, 02, 03...012, 013, 014...0123, 0124, 0125...01234, 012345, 0123456...

Note:

• Time complexity = O(10*9*8*7*...*1) = O(1), the worst case is that n = 10, so there are 10 levels recursions. The first level there are 10 digits can be chosen, the second level there are 9 digits can be chosen, the third level there are 8 digits can be chosen...... so the worst case the number of recursions is 10 * 9 * 8 * ... * 1 = constant. So time complexity = O(1).