MediumRating 1741
1079. Letter Tile Possibilities
hash-tablestringbacktrackingcounting
解題說明
Letter Tile Possibilities
題目描述： 有一組字母瓦片，每塊上印有一個字母。求能排列出多少種不同的非空字母序列。
解題思路：
- 回溯 + 頻率計數：先統計每個字母出現的次數。
- 用回溯法枚舉所有可能的序列。在每一步，可以選擇任何一個剩餘數量 > 0 的字母加入序列。
- 每加入一個字母就是一個新的合法序列（因為要計算所有長度的排列）。
- 由於是基於頻率而非位置的回溯，自然避免了重複排列的問題。
- 例如有 2 個 A，只需「選 A 一次，count 從 2 減到 1」和「選 A 第二次，count 從 1 減到 0」，不會重複。
C++ 解法
複雜度分析
時間複雜度：O(n!) — 最壞情況下所有字母不同，排列數為 n! + n!/1! + ... 級別
空間複雜度：O(n) — 遞迴深度最多為字母總數 n
虛擬碼
1. Count frequency of each letter (26 slots for A-Z)
2. backtrack(count):
a. total = 0
b. For each letter i (A to Z):
- If count[i] > 0:
- Decrement count[i]
- total += 1 (this partial sequence is valid)
- total += backtrack(count) (extend with more letters)
- Increment count[i] (undo choice)
c. Return total
3. Return backtrack(count)其他解法
-
數學公式（排列組合）：對於每種選擇的字母子集和數量，用多重排列公式 n! / (n1! * n2! * ... * nk!) 計算。需要枚舉所有可能的字母選取方式，較為複雜但理論上更高效。
-
位元遮罩枚舉 + 去重：用 bitmask 枚舉選擇哪些瓦片，然後用集合去重。時間複雜度 O(2^n * n)，在 n <= 7 時可行但效率較差。
延伸思考
- 如果瓦片上的字母可以重複使用（無限供應），答案會是什麼？
- 如果要求序列是回文的，有多少種可能？
- 如果字母表不是 26 個英文字母而是自定義集合呢？