473. Matchsticks to Square

Medium
Description

給定一個整數陣列 matchsticks，每個元素代表一根火柴的長度。判斷是否能用所有火柴拼成一個正方形（每根火柴恰好用一次，不能折斷）。

Example:

Input: matchsticks = [1,1,2,2,2] Output: true

Intuition#

核心思路：將火柴分成 4 組，每組的總和等於周長 / 4，用回溯法嘗試分配。

  • 先算總和是否能被 4 整除，否則直接回傳 false
  • 每邊目標長度 = 總和 / 4
  • 把火柴分配到 4 條邊，回溯嘗試
  • 關鍵優化：降序排序（大的先放），加速剪枝

Approaches#

⭐1: 回溯 + 剪枝#

  • 概念: 嘗試將每根火柴放入 4 條邊中的一條，若某邊超過目標則回溯。降序排序大幅減少搜索
  • 時間複雜度: O(4^n) 最差情況，但剪枝後遠小於此
  • 空間複雜度: 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 個桶
  • 關鍵技巧: 降序排序是關鍵優化（大元素先放可以提早發現不合法的分支）；跳過相同邊長度的桶避免重複搜索。此 pattern 同樣適用於 698. Partition to K Equal Sum Subsets
Backward 131. Palindrome Partitioning 698. Partition to K Equal Sum Subsets Forward