Medium
473. Matchsticks to Square
arraydynamic-programmingbacktrackingbit-manipulationbitmask
解題說明
Matchsticks to Square
題目描述：
給定一個整數陣列 matchsticks，代表每根火柴的長度。判斷能否將所有火柴恰好分成四組，使每組長度之和相等（即組成一個正方形）。
解題思路：
使用回溯法（DFS + 剪枝）。設邊長 side = sum / 4。
- 若總和不是 4 的倍數，直接回傳 false。
- 將火柴從大到小排序（大的先放，更早觸發剪枝）。
- 維護四個桶
sides[4]，每個桶代表正方形的一條邊。 - 對每根火柴嘗試放入四個桶之一：
- 剪枝：若放入後超過
side，跳過。 - 剪枝：若當前桶的值與前一個相同，跳過（避免對稱重複）。
- 剪枝：若放入後超過
- 若所有火柴都成功放入，回傳 true。
C++ 解法
複雜度分析
時間複雜度：O(4^n) 最壞情況 — 每根火柴有 4 種選擇。但排序與剪枝大幅減少實際搜尋空間。
空間複雜度：O(n) — 遞迴深度為 n（火柴數量），加上排序所需空間。
虛擬碼
1. Compute sum of all matchsticks
2. If sum % 4 != 0, return false
3. side = sum / 4
4. Sort matchsticks in descending order
5. If largest matchstick > side, return false
6. Initialize sides[4] = {0, 0, 0, 0}
7. backtrack(index):
a. If index == n: return all sides == target
b. For each bucket i from 0 to 3:
- If sides[i] + matchstick[index] > side: skip
- If i > 0 and sides[i] == sides[i-1]: skip (prune symmetry)
- sides[i] += matchstick[index]
- If backtrack(index + 1): return true
- sides[i] -= matchstick[index]
c. Return false其他解法
Bitmask DP：用 bitmask 表示已使用的火柴子集。dp[mask] 記錄已使用的火柴能否恰好填滿若干條完整的邊。用 curSum 追蹤當前未滿的邊的累積長度。時間 O(n * 2^n)，空間 O(2^n)。n <= 15 時可行，適合對稱剪枝困難的情況，但空間消耗較大。
暴力枚舉所有劃分：列舉所有將 n 根火柴分成四組的方式。時間 O(4^n)，無剪枝則非常慢。僅作為理解問題的起點。
延伸思考
- 若要分成 k 組（k 不固定）使每組和相等，如何推廣此算法？（LeetCode 698）
- 降序排列為什麼能有效剪枝？能否從數學上估計剪枝的效果？
- Bitmask DP 與回溯法在什麼情況下各自更優？n 的閾值大概是多少？