题目：
如果一个正整数每一个数位都是 互不相同 的，我们称它是 特殊整数 。
给你一个 正 整数 n ，请你返回区间 [1, n] 之间特殊整数的数目。
示例 1：
输入：n = 20
输出：19
解释：1 到 20 之间所有整数除了 11 以外都是特殊整数。所以总共有 19 个特殊整数。
示例 2：
输入：n = 5
输出：5
解释：1 到 5 所有整数都是特殊整数。
示例 3：
输入：n = 135
输出：110
解释：从 1 到 135 总共有 110 个整数是特殊整数。
不特殊的部分数字为：22 ，114 和 131 。
提示：
1 <= n <= 2 * 109
思路：
要返回区间 [1, n] 之间的特殊整数的数目，即小于等于 n 的特殊整数的数目。记 n 十进制表示下位数为 k，我们考虑两种情况：
位数小于 k 的特殊整数。
位数等于 k 的特殊整数。
对于位数小于 k 的情况，分别计算位数为 1 到 k − 1 的情况下特殊整数的数量。考虑位数为 k0(k0 < k) 的情况。因为 k0 < k，所以任意放置数位上的数字，都能满足小于等于 n 的条件。只需保证每一数位都互不相同。用组合数学的思路求解特殊整数的数量，从最高位开始考虑，可以有 9 种选择（除 0 外的任何整数），次高位也有 9 种选择（除最高位外的任何整数），接下来的数位的选择则依次减少 1。把这些选择的可能性全部相乘则是位数为 k0 的特殊整数的数量。
接下来考虑位数等于 k 的特殊整数。相同位数的数字比较大小，是从最高位开始比较，若不同，则最高位大的数字大；若相同，则比较次高位。次高位的比较原则和最高位一样。因此，我们在计算小于等于 n 的特殊整数时，也需要按照这个原则。函数 dp(mask, prefixSmaller) 用来计算以某些数字组合为前缀的特殊整数的数量。整数 mask 即表示了前缀中使用过的数字，二进制表示下，从最低位开始，第 i 为如果为 1 则表示数字 i 已经被使用过，在接下来的后缀中不能使用。布尔值 prefixSmaller 表示当前的前缀是否小于 n 的前缀，如果是，则接下来的数字可以任意选择。如果不是，即当前的前缀等于 n 的前缀，则接下来的数字只能小于或者等于 n 同数位的数字。最后调用 dp(0, false) 则为位数等于 k 的特殊整数的数量。
最后把这两部分相加即可。
代码：
class Solution {
public:
unordered_map<int, int> memo;
int countSpecialNumbers(int n) {
string nStr = to_string(n);
int res = 0;
int prod = 9;
for (int i = 0; i < nStr.size() - 1; i++) {
res += prod;
prod *= 9 - i;
}
res += dp(0, false, nStr);
return res;
}
int dp(int mask, bool prefixSmaller, const string &nStr) {
if (__builtin_popcount(mask) == nStr.size()) { // 返回输入数据中，二进制中‘1’的个数
return 1;
}
int key = mask * 2 + (prefixSmaller ? 1 : 0);
if (!memo.count(key)) {
int res = 0;
int lowerBound = mask == 0 ? 1 : 0; // 确定当前枚举的位置的下界
int upperBound = prefixSmaller ? 9 : nStr[__builtin_popcount(mask)] - '0'; // 确定当前枚举的位置的上界
for (int i = lowerBound; i <= upperBound; i++) {
if (((mask >> i) & 1) == 0) { // 这个数字没有使用过
res += dp(mask | (1 << i), prefixSmaller || i < upperBound, nStr);
}
}
memo[key] = res;
}
return memo[key];
}
};