C++ digit dp with backtracking
\nclass Solution {\npublic:\n    \n    int anotherdp[15][2];\n    \n    int total(string x,int n,bool tight,set<int> &s){\n        if(n==0){\n            return
```\nclass Solution {\npublic:\n    \n    int anotherdp[15][2];\n    \n    int total(string x,int n,bool tight,set<int> &s){\n        if(n==0){\n            return 1;\n        }\n        if(anotherdp[n][tight]!=-1){\n            return anotherdp[n][tight];\n        }\n        int ub = (tight==1) ? x[x.length()-n]-\'0\' : 9;\n        int res=0;\n        for(int i=0;i<=ub;i++){\n            if(s.empty() && i==0) continue;\n            else if(s.find(i)==s.end()){\n                s.insert(i);\n                res+=total(x,n-1,(tight & (i==ub)),s);\n                s.erase(s.find(i));\n            }\n        }\n        return (anotherdp[n][tight]=res);\n    }\n    \n    int numDupDigitsAtMostN(int N) {\n        if(N<=10){\n            return 0;\n        }\n        int n = log10(N);\n        int dp[n+1];\n        memset(dp,0,sizeof(dp));\n        dp[1] = 9;\n        int x=9;\n        int y=9;\n        for(int i=2;i<=n;i++){\n            x*=y;\n            y--;\n            dp[i] = x;\n            dp[i]+=dp[i-1];\n        }\n        set<int> s;\n        s.clear(); \n        string xx = to_string(N);\n        memset(anotherdp,-1,sizeof(anotherdp));\n        int temp = total(xx,xx.length(),1,s);\n        return N-(dp[n]+temp);\n    }\n};\n```
[]