題目描述: 有一組字母瓦片,每塊上印有一個字母。求能排列出多少種不同的非空字母序列。
解題思路:
時間複雜度: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 時可行但效率較差。