C++ backtracking solution


  • 0
    C

    Since the problem description mentioned backtracking, here is my backtracking version of the solution. I have verified the correctness of this solution using brutal force algorithm. However, the time complexity is O(n!). It fails the input n=8 due to the Time Limit Exceeded error.

    class Solution {
    public:
        int countNumbersWithUniqueDigits(int n) {
            total = 0;
            unordered_set<int> mask;
            for (int i = 0; i <= n; i++) {
                backtracking(i, 0, mask);
            }
            return total;
        }
        
    private:
        int total;
        
        void backtracking(int n, int count, unordered_set<int>& mask) {
            if (count == n) {
                total++;
                return;
            }
            int start = count == 0 ? 1 : 0;
            for (int i = start; i <= 9; i++) {
                if (mask.find(i) != mask.end()) continue;
                mask.insert(i);
                backtracking(n, count + 1, mask);
                mask.erase(i);
            }
        }
    };
    

Log in to reply
 

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