<p>Given an integer <code>n</code>, return the count of all numbers with unique digits, <code>x</code>, where <code>0 &lt;= x &lt; 10<sup>n</sup></code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 91
<strong>Explanation:</strong> The answer should be the total numbers in the range of 0 &le; x &lt; 100, excluding 11,22,33,44,55,66,77,88,99
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 0
<strong>Output:</strong> 1
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 8</code></li>
</ul>

class Solution {
  int helper(string &s, int ind, int tight, int mask, int dp[][1024][2])
    {
        // check if mask is not zero, means at least we have checked a non-zero number
        if (ind == s.size())
            return mask!=0;

        if (dp[ind][mask][tight] != -1)
            return dp[ind][mask][tight];
        
        int limit = tight == 1 ? s[ind] - '0' : 9;
        int ans = 0;
        for (int i = 0; i <= limit; i++)
        {
            // go for position i and check if there is 1 or not
            // if certain digit is already used go for another digit
            if(mask & (1 << i)) 
                continue;
             
            // (mask | (1 << i)) , means go on ith position and set the bit
            //(mask == 0 && i == 0) means it is till now leading zeroes
            int newMask = (mask == 0 && i == 0 ? mask : (mask | (1 << i)));
            int newTight = tight & (i == s[ind] - '0');
            ans += helper(s, ind + 1, newTight,newMask , dp);
        }
        return dp[ind][mask][tight] = ans;
    }
public:
    int countNumbersWithUniqueDigits(int n) {
        //index,mask(max can be 2 power 11),tight
        int dp[11][1024][2];
        memset(dp, -1, sizeof(dp));
        int number = pow(10,n)-1;
        string r1 = to_string(number);
        // one added for the zero
        return helper(r1, 0, 1, 0, dp)+1; 
    }
};

7600