Medium

题目描述

给你一个整数数组 matchsticks，其中 matchsticks[i] 是第 i 根火柴棒的长度。你要用所有的火柴棒拼成一个正方形。你不能折断火柴棒，只能把它们连接起来，且每根火柴棒都要用到。

只有能拼成一个正方形时才返回 true，否则返回 false。

示例 1：

输入：matchsticks = [1,1,2,2,2]
输出：true
解释：能拼成一个边长为 2 的正方形，每边由两根火柴棒组成。

示例 2：

输入：matchsticks = [3,3,3,3,4]
输出：false
解释：不能用所有火柴棒拼成一个正方形。

约束：

  • 1 <= matchsticks.length <= 15
  • 1 <= matchsticks[i] <= 10^8

解题思路

这道题可以转化为将火柴棒数组分成4个相等长度的子集的问题。

基本思路分析：

  1. 首先计算所有火柴棒的总长度，如果不能被4整除，直接返回false
  2. 每条边的目标长度为总长度的1/4
  3. 使用回溯算法，对每根火柴棒尝试放入4条边中的任意一条

优化策略：

  1. 先将火柴棒按长度降序排序，这样可以更早地剪枝
  2. 当某条边的长度超过目标长度时，立即回溯
  3. 避免重复计算：当两条边长度相同时，不需要重复尝试

算法实现：

  • 使用四个变量记录四条边当前的长度
  • 递归尝试将每根火柴棒放入四条边之一
  • 如果所有火柴棒都分配完且四条边长度相等，返回true

这种方法的时间复杂度虽然是指数级，但由于数据规模小（n≤15），加上剪枝优化，实际运行效率可以接受。

代码实现

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = 0;
        for (int stick : matchsticks) {
            sum += stick;
        }
        if (sum % 4 != 0) return false;
        
        int target = sum / 4;
        sort(matchsticks.begin(), matchsticks.end(), greater<int>());
        
        vector<int> sides(4, 0);
        return backtrack(matchsticks, 0, sides, target);
    }
    
private:
    bool backtrack(vector<int>& matchsticks, int index, vector<int>& sides, int target) {
        if (index == matchsticks.length) {
            return sides[0] == target && sides[1] == target && 
                   sides[2] == target && sides[3] == target;
        }
        
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (backtrack(matchsticks, index + 1, sides, target)) {
                    return true;
                }
                sides[i] -= matchsticks[index];
            }
            
            // 剪枝：如果当前边长为0，后面相同长度的边不需要再试
            if (sides[i] == 0) break;
        }
        
        return false;
    }
};

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        
        target = total // 4
        matchsticks.sort(reverse=True)
        
        sides = [0] * 4
        
        def backtrack(index):
            if index == len(matchsticks):
                return all(side == target for side in sides)
            
            for i in range(4):
                if sides[i] + matchsticks[index] <= target:
                    sides[i] += matchsticks[index]
                    if backtrack(index + 1):
                        return True
                    sides[i] -= matchsticks[index]
                
                # 剪枝：如果当前边长为0，后面相同长度的边不需要再试
                if sides[i] == 0:
                    break
            
            return False
        
        return backtrack(0)

public class Solution {
    public bool Makesquare(int[] matchsticks) {
        int sum = matchsticks.Sum();
        if (sum % 4 != 0) return false;
        
        int target = sum / 4;
        Array.Sort(matchsticks, (a, b) => b.CompareTo(a));
        
        int[] sides = new int[4];
        return Backtrack(matchsticks, 0, sides, target);
    }
    
    private bool Backtrack(int[] matchsticks, int index, int[] sides, int target) {
        if (index == matchsticks.Length) {
            return sides[0] == target && sides[1] == target && 
                   sides[2] == target && sides[3] == target;
        }
        
        for (int i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (Backtrack(matchsticks, index + 1, sides, target)) {
                    return true;
                }
                sides[i] -= matchsticks[index];
            }
            
            // 剪枝：如果当前边长为0，后面相同长度的边不需要再试
            if (sides[i] == 0) break;
        }
        
        return false;
    }
}

var makesquare = function(matchsticks) {
    const sum = matchsticks.reduce((a, b) => a + b, 0);
    if (sum % 4 !== 0) return false;
    
    const target = sum / 4;
    matchsticks.sort((a, b) => b - a);
    
    if (matchsticks[0] > target) return false;
    
    const sides = [0, 0, 0, 0];
    
    function backtrack(index) {
        if (index === matchsticks.length) {
            return sides[0] === sides[1] && sides[1] === sides[2] && sides[2] === sides[3];
        }
        
        for (let i = 0; i < 4; i++) {
            if (sides[i] + matchsticks[index] <= target) {
                sides[i] += matchsticks[index];
                if (backtrack(index + 1)) return true;
                sides[i] -= matchsticks[index];
            }
            if (sides[i] === 0) break;
        }
        
        return false;
    }
    
    return backtrack(0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(4^n)n为火柴棒数量，最坏情况每根火柴棒都有4种选择，实际会通过剪枝大幅优化
空间复杂度O(n)递归调用栈的深度为n，额外使用O(1)空间存储四条边的长度

相关题目