題目描述:
給定一個整數陣列 matchsticks,代表每根火柴的長度。判斷能否將所有火柴恰好分成四組,使每組長度之和相等(即組成一個正方形)。
解題思路:
使用回溯法(DFS + 剪枝)。設邊長 side = sum / 4。
sides[4],每個桶代表正方形的一條邊。side,跳過。時間複雜度: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 falseBitmask DP:用 bitmask 表示已使用的火柴子集。dp[mask] 記錄已使用的火柴能否恰好填滿若干條完整的邊。用 curSum 追蹤當前未滿的邊的累積長度。時間 O(n * 2^n),空間 O(2^n)。n <= 15 時可行,適合對稱剪枝困難的情況,但空間消耗較大。
暴力枚舉所有劃分:列舉所有將 n 根火柴分成四組的方式。時間 O(4^n),無剪枝則非常慢。僅作為理解問題的起點。