活字印刷【LC1079】
你有一套活字字模
tiles，其中每个字模上都刻有一个字母tiles[i]。返回你可以印出的非空字母序列的数目。**注意：**本题中，每个活字字模只能使用一次。
我反正是写的相当暴力
计数+回溯
- 思路：
为了构成不同的字母序列，每一个位置相同的字母只能使用一次。
- 因此可以预处理每个字符出现的次数，然后使用回溯枚举每个位置字母的使用情况，并使用全局变量记录结果。
- 每层有一个选择时，数量加1
- 实现
class Solution { public int numTilePossibilities(String tiles) { int[] cnt = new int[26]; for (char c : tiles.toCharArray()) { ++cnt[c - 'A']; } return dfs(cnt); } private int dfs(int[] cnt) { int res = 0; for (int i = 0; i < cnt.length; ++i) { if (cnt[i] > 0) { ++res; --cnt[i]; res += dfs(cnt); ++cnt[i]; } } return res; } } 作者：ylb 链接：https://leetcode.cn/problems/letter-tile-possibilities/solutions/2275545/python3javacgotypescript-yi-ti-yi-jie-ji-cxp7/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { private static final int MX = 8; private static final int[][] c = new int[MX][MX]; static { for (int i = 0; i < MX; i++) { c[i][0] = c[i][i] = 1; for (int j = 1; j < i; j++) c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; // 预处理组合数 } } public int numTilePossibilities(String tiles) { int[] counts = new int[26];// 统计每个字母的出现次数 for (var c : tiles.toCharArray()) counts[c - 'A']++; int m = counts.length, n = tiles.length(); var f = new int[m + 1][n + 1]; f[0][0] = 1; // 构造空序列的方案数 int i = 1; for (var cnt : counts) { // 枚举第 i 种字母 for (int j = 0; j <= n; j++) // 枚举序列长度 j for (int k = 0; k <= j && k <= cnt; k++) // 枚举第 i 种字母选了 k 个 f[i][j] += f[i - 1][j - k] * c[j][k]; i++; } int ans = 0; for (int j = 1; j <= n; j++) ans += f[m][j]; return ans; } } 作者：灵茶山艾府 链接：https://leetcode.cn/problems/letter-tile-possibilities/solutions/2275356/on2-ji-shu-dppythonjavacgo-by-endlessche-hmez/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
