給定一個整數陣列
matchsticks，每個元素代表一根火柴的長度。判斷是否能用所有火柴拼成一個正方形（每根火柴恰好用一次，不能折斷）。
Example:
Input: matchsticks = [1,1,2,2,2] Output: true
Intuition
TIP
核心思路：將火柴分成 4 組，每組的總和等於周長 / 4，用回溯法嘗試分配。
- 先算總和是否能被 4 整除，否則直接回傳 false
- 每邊目標長度 = 總和 / 4
- 把火柴分配到 4 條邊，回溯嘗試
- 關鍵優化：降序排序（大的先放），加速剪枝
Approaches
1. Bitmask DP — O(2^n · n) / O(2^n)
- Idea:
dp[mask]= 用掉 mask 這些火柴後、當前未填滿那條邊已放的長度（mod side）；填滿一邊就歸 0 進下一邊 - Time:
O(2^n · n) - Space:
O(2^n)
class Solution {
fun makesquare(matchsticks: IntArray): Boolean {
val total = matchsticks.sum()
if (total % 4 != 0) return false
val side = total / 4
if (matchsticks.any { it > side }) return false
val n = matchsticks.size
val full = (1 shl n) - 1
val dp = IntArray(1 shl n) { -1 } // -1 = 不可達
dp[0] = 0
for (mask in 0..full) {
if (dp[mask] == -1) continue
for (i in 0 until n) {
if (mask and (1 shl i) != 0) continue
if (dp[mask] + matchsticks[i] > side) continue
val next = mask or (1 shl i)
if (dp[next] == -1) dp[next] = (dp[mask] + matchsticks[i]) % side
}
}
return dp[full] == 0
}
}⭐ 2. Backtracking + Pruning — O(4^n) / O(n)
- Idea: 嘗試將每根火柴放入 4 條邊中的一條，若某邊超過目標則回溯。降序排序大幅減少搜索
- Time:
O(4^n)最差情況，但剪枝後遠小於此 - Space:
O(n)- 遞迴深度
class Solution {
fun makesquare(matchsticks: IntArray): Boolean {
val total = matchsticks.sum()
if (total % 4 != 0) return false
val side = total / 4
// 降序排序，讓大的先嘗試，提早剪枝
matchsticks.sortDescending()
// 若最大的火柴超過邊長，不可能
if (matchsticks[0] > side) return false
val sides = IntArray(4)
fun backtrack(idx: Int): Boolean {
if (idx == matchsticks.size) {
return sides.all { it == side }
}
val seen = mutableSetOf<Int>()
for (i in 0 until 4) {
// 剪枝：放入後超過邊長
if (sides[i] + matchsticks[idx] > side) continue
// 剪枝：相同長度的邊不重複嘗試
if (sides[i] in seen) continue
seen.add(sides[i])
sides[i] += matchsticks[idx]
if (backtrack(idx + 1)) return true
sides[i] -= matchsticks[idx]
}
return false
}
return backtrack(0)
}
}🔑 Takeaways
- Pattern: K 等分問題 → 回溯分配到 K 個桶
- Key trick: 降序排序是關鍵優化（大元素先放可以提早發現不合法的分支）；跳過相同邊長度的桶避免重複搜索。此 pattern 同樣適用於 698. Partition to K Equal Sum Subsets