Two C++ solutions: Backtracking and DP (4 lines only)


  • 4
    C

    DP solution:

    class Solution {
    public:
        int countNumbersWithUniqueDigits(int n) {
            vector<int> tbl(min(n,10)+1, 1);
            for (int i = 1; i <= min(n,10); i++)
                tbl[i] = tbl[i-1] * (i == 1? 9: (9-i+2));
            return accumulate(tbl.begin(), tbl.end(), 0);
        }
    };
    

    Backtracking solution

    class Solution {
    public:
        int countNumbersWithUniqueDigits(int n) {
            bool visit[10] = {false};
            int count = 0;
            for (int i = 0; i <= min(10,n); i++)
                count += DFS(i, 0, visit);
            return count;
        }
    private:
        int DFS(int target, int idx, bool* visit) {
            if (idx == target)
                return 1;
    
            int count = 0;
            for (int i = idx?0:1; i < 10; i++) {
                if (!visit[i]) {
                    visit[i] = true;
                    count += DFS(target, idx+1, visit);
                    visit[i] = false;
                }
            }
            return count;
        }
    };

  • 0
    C

    Can you explain your backtracking method? Thanks


  • 0
    A

    Can you tell what min(10,n) does?


  • 0
    C

    @anwarshah after 10 digit, there must be one pair of duplicate digit, which can't be counted.


  • 0
    J

    nice solution!


Log in to reply
 

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