1079. Letter Tile Possibilities ------M

 You have n  tiles, where each tile has one letter tiles[i] printed on it.

Return the number of possible non-empty sequences of letters you can make using the letters printed on those tiles.

 

Example 1:

Input: tiles = "AAB"
Output: 8
Explanation: The possible sequences are "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA".

Example 2:

Input: tiles = "AAABBC"
Output: 188

Example 3:

Input: tiles = "V"
Output: 1

 

Constraints:

• 1 <= tiles.length <= 7
• tiles consists of uppercase English letters.

A：

就还是递归。

class Solution {

public:

int numTilePossibilities(string tiles) {

int n = tiles.length();

vector<int> C(26, 0);

for (auto ch : tiles) {

C[ch - 'A'] += 1;

}

int res = 0;

for (int c = 1; c <= n; c++) {

res += helper(C, 0, c);

}

return res;

}

private:

int helper(vector<int>& C, int start, int len) {

if (len < 0)

return 0;

if (start >= C.size())

return len == 0 ? 1 : 0;

int res = 0;

for (int used = 0; used <= C[start]; used++) {

auto nextRes = helper(C, start + 1, len - used);

res += getC_n_k(len, used) * nextRes;

}

return res;

}

int getC_n_k(int n, int k) {

// k >=0 n >=k

int res = 1;

if (k <= 0)

return 1;

for (int i = 0; i < k; i++) {

res *= (n - i);

}

for (int i = 0; i < k; i++) {

res /= (k - i);

}

return res;

}

};

果然是刷题要看状态。 昨天晚上凌搞错了。一时间也没搞明白怎么改。

就算了去睡觉了。也根本没再思考。 结果醒来，直接看到了问题。 一到一分钟，就改好了。

核心问题在于结束的状态。需要返回0 而不是1