![0.png](https://developer.qcloudimg.com/http-save/yehe-8235133/3f4ee5be9c9237e76ec87f46c5871ae5.png)

## 摘要

这道题其实挺有意思的，它让我们用一堆长度不同的火柴棒，看看能不能拼成一个完整的正方形。听起来简单，但实际做起来还是需要一些技巧的。我们需要用回溯算法，尝试把每根火柴放到正方形的四条边中的一条，看看能不能正好填满。今天我们就用 Swift 来搞定这道题，顺便聊聊它在实际开发中能用到哪些场景。

## 描述

题目要求很简单：给你一个整数数组 `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] <= 108`

这道题的核心思路是什么呢？首先，我们要知道，如果所有火柴的总长度不能被 4 整除，那肯定拼不成正方形，直接返回 `false`。然后，我们需要把火柴分配到四条边上，每条边的长度应该等于总长度除以 4。接下来就是回溯算法登场了，我们尝试把每根火柴放到四条边中的一条，如果某条边超过了目标长度，就剪枝，如果所有火柴都分配完了，而且每条边都正好等于目标长度，那就返回 `true`。

## 题解答案

下面是完整的 Swift 解决方案：

```swift
class Solution {
    func makesquare(_ matchsticks: [Int]) -> Bool {
        // 计算所有火柴的总长度
        let totalLength = matchsticks.reduce(0, +)
        
        // 如果总长度不能被 4 整除，肯定拼不成正方形
        guard totalLength % 4 == 0 else {
            return false
        }
        
        // 计算每条边的目标长度
        let targetLength = totalLength / 4
        
        // 如果任何一根火柴的长度超过目标长度，肯定拼不成
        if matchsticks.contains(where: { $0 > targetLength }) {
            return false
        }
        
        // 对火柴长度进行降序排序，这样可以更快地剪枝
        let sortedMatchsticks = matchsticks.sorted(by: >)
        
        // 初始化四条边的当前长度
        var sides = [0, 0, 0, 0]
        
        // 使用回溯算法尝试分配火柴
        return backtrack(sortedMatchsticks, 0, &sides, targetLength)
    }
    
    // 回溯函数
    private func backtrack(_ matchsticks: [Int], _ index: Int, _ sides: inout [Int], _ targetLength: Int) -> Bool {
        // 如果所有火柴都分配完了，检查是否每条边都等于目标长度
        if index == matchsticks.count {
            return sides.allSatisfy { $0 == targetLength }
        }
        
        let currentMatchstick = matchsticks[index]
        
        // 尝试将当前火柴放到四条边中的一条
        for i in 0..<4 {
            // 如果当前边加上这根火柴的长度超过目标长度，跳过（剪枝）
            if sides[i] + currentMatchstick > targetLength {
                continue
            }
            
            // 如果当前边和前面的边长度相同，跳过（避免重复计算）
            // 这是一个重要的优化，因为四条边是对称的
            if i > 0 && sides[i] == sides[i - 1] {
                continue
            }
            
            // 将当前火柴放到第 i 条边
            sides[i] += currentMatchstick
            
            // 递归尝试分配下一根火柴
            if backtrack(matchsticks, index + 1, &sides, targetLength) {
                return true
            }
            
            // 回溯：撤销刚才的操作
            sides[i] -= currentMatchstick
        }
        
        // 如果所有尝试都失败了，返回 false
        return false
    }
}
```

## 题解代码分析

让我们一步步分析这个解决方案：

### 1. 基础判断和预处理

```swift
let totalLength = matchsticks.reduce(0, +)
guard totalLength % 4 == 0 else {
    return false
}
```

首先，我们计算所有火柴的总长度。如果总长度不能被 4 整除，那肯定拼不成正方形，因为正方形的四条边长度必须相等。这是一个很重要的剪枝条件，可以让我们在早期就排除掉很多不可能的情况。

```swift
let targetLength = totalLength / 4
if matchsticks.contains(where: { $0 > targetLength }) {
    return false
}
```

然后，我们计算每条边的目标长度。如果任何一根火柴的长度超过目标长度，那肯定拼不成，因为一根火柴不能跨越多条边。这也是一个重要的剪枝条件。

```swift
let sortedMatchsticks = matchsticks.sorted(by: >)
```

接下来，我们对火柴长度进行降序排序。为什么要这样做呢？因为如果我们先把长的火柴分配好，可以更快地发现不可能的情况，从而进行剪枝。比如，如果最长的火柴都放不下，那后面的短火柴就更不用说了。

### 2. 回溯算法的核心逻辑

```swift
var sides = [0, 0, 0, 0]
return backtrack(sortedMatchsticks, 0, &sides, targetLength)
```

我们用一个数组 `sides` 来记录四条边的当前长度，初始值都是 0。然后调用回溯函数，从第一根火柴开始尝试分配。

```swift
private func backtrack(_ matchsticks: [Int], _ index: Int, _ sides: inout [Int], _ targetLength: Int) -> Bool {
    if index == matchsticks.count {
        return sides.allSatisfy { $0 == targetLength }
    }
```

回溯函数的核心逻辑是：如果所有火柴都分配完了，检查是否每条边都等于目标长度。如果都相等，返回 `true`，否则返回 `false`。

```swift
let currentMatchstick = matchsticks[index]

for i in 0..<4 {
    if sides[i] + currentMatchstick > targetLength {
        continue
    }
```

然后，我们尝试将当前火柴放到四条边中的一条。如果某条边加上当前火柴的长度超过目标长度，就跳过这条边，因为这样肯定拼不成。

```swift
if i > 0 && sides[i] == sides[i - 1] {
    continue
}
```

这是一个很重要的优化。如果当前边和前面的边长度相同，我们跳过这条边，因为四条边是对称的，如果前面的边已经尝试过了，当前边就不用再试了。这样可以避免重复计算，大大提高效率。

```swift
sides[i] += currentMatchstick

if backtrack(matchsticks, index + 1, &sides, targetLength) {
    return true
}

sides[i] -= currentMatchstick
```

接下来，我们将当前火柴放到第 `i` 条边，然后递归尝试分配下一根火柴。如果递归返回 `true`，说明找到了解决方案，直接返回 `true`。否则，我们撤销刚才的操作（回溯），尝试下一条边。

### 3. 为什么这个算法能工作？

回溯算法的核心思想是：尝试所有可能的分配方式，如果某条路径走不通，就回退到上一步，尝试其他路径。在这个问题中，我们尝试把每根火柴放到四条边中的一条，如果某条路径能成功分配所有火柴，就返回 `true`，否则继续尝试其他路径。

### 4. 优化技巧

1. **降序排序**：先把长的火柴分配好，可以更快地发现不可能的情况。
2. **剪枝**：如果某条边加上当前火柴的长度超过目标长度，直接跳过。
3. **避免重复计算**：如果当前边和前面的边长度相同，跳过当前边，因为四条边是对称的。

## 示例测试及结果

让我们用几个例子来测试一下这个解决方案：

### 示例 1：matchsticks = [1,1,2,2,2]

```swift
let solution = Solution()
let result1 = solution.makesquare([1,1,2,2,2])
print("示例 1 结果: \(result1)")  // 输出: true
```

**执行过程分析：**

1. 总长度 = 1 + 1 + 2 + 2 + 2 = 8，能被 4 整除，目标长度 = 2
2. 排序后：[2, 2, 2, 1, 1]
3. 分配过程：
   - 第一根火柴（长度 2）放到边 0：sides = [2, 0, 0, 0]
   - 第二根火柴（长度 2）放到边 1：sides = [2, 2, 0, 0]
   - 第三根火柴（长度 2）放到边 2：sides = [2, 2, 2, 0]
   - 第四根火柴（长度 1）放到边 0：sides = [3, 2, 2, 0]（超过目标长度，回溯）
   - 第四根火柴（长度 1）放到边 1：sides = [2, 3, 2, 0]（超过目标长度，回溯）
   - 第四根火柴（长度 1）放到边 2：sides = [2, 2, 3, 0]（超过目标长度，回溯）
   - 第四根火柴（长度 1）放到边 3：sides = [2, 2, 2, 1]
   - 第五根火柴（长度 1）放到边 3：sides = [2, 2, 2, 2]
   - 所有火柴分配完成，每条边都等于目标长度 2，返回 `true`

### 示例 2：matchsticks = [3,3,3,3,4]

```swift
let result2 = solution.makesquare([3,3,3,3,4])
print("示例 2 结果: \(result2)")  // 输出: false
```

**执行过程分析：**

1. 总长度 = 3 + 3 + 3 + 3 + 4 = 16，能被 4 整除，目标长度 = 4
2. 排序后：[4, 3, 3, 3, 3]
3. 分配过程：
   - 第一根火柴（长度 4）放到边 0：sides = [4, 0, 0, 0]
   - 第二根火柴（长度 3）放到边 1：sides = [4, 3, 0, 0]
   - 第三根火柴（长度 3）放到边 2：sides = [4, 3, 3, 0]
   - 第四根火柴（长度 3）放到边 3：sides = [4, 3, 3, 3]
   - 第五根火柴（长度 3）无法放到任何一条边（因为每条边加上 3 都会超过目标长度 4）
   - 回溯尝试其他分配方式，但都无法成功，返回 `false`

### 示例 3：matchsticks = [5,5,5,5,4,4,4,4,3,3,3,3]

```swift
let result3 = solution.makesquare([5,5,5,5,4,4,4,4,3,3,3,3])
print("示例 3 结果: \(result3)")  // 输出: true
```

**执行过程分析：**

1. 总长度 = 5×4 + 4×4 + 3×4 = 20 + 16 + 12 = 48，能被 4 整除，目标长度 = 12
2. 排序后：[5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]
3. 可以成功分配，比如：
   - 边 0：5 + 4 + 3 = 12
   - 边 1：5 + 4 + 3 = 12
   - 边 2：5 + 4 + 3 = 12
   - 边 3：5 + 4 + 3 = 12
   - 返回 `true`

## 时间复杂度

这个算法的时间复杂度主要取决于回溯过程中尝试的次数。最坏情况下，我们需要尝试所有可能的分配方式。

- **最坏时间复杂度**：O(4^n)，其中 n 是火柴的数量。因为每根火柴都有 4 种选择（放到四条边中的一条），所以总共有 4^n 种可能的分配方式。
- **实际时间复杂度**：由于我们使用了剪枝和优化技巧（降序排序、避免重复计算），实际运行时间会大大减少。在大多数情况下，时间复杂度会远小于 O(4^n)。

## 空间复杂度

- **空间复杂度**：O(n)，其中 n 是火柴的数量。主要空间消耗来自：
  1. 递归调用栈的深度，最多为 n（每根火柴对应一层递归）
  2. `sides` 数组，固定大小为 4
  3. 排序后的数组，大小为 n

由于题目中 `matchsticks.length <= 15`，所以空间复杂度是可以接受的。

## 实际应用场景

这道题虽然看起来像是一个纯粹的算法题，但在实际开发中，类似的思路还是很有用的：

### 1. 资源分配问题

比如，在服务器资源分配中，我们可能需要将多个任务分配到多个服务器上，每个服务器有固定的容量。我们可以用类似的回溯算法来找到最优的分配方案。

```swift
// 伪代码示例
func allocateTasks(_ tasks: [Task], _ servers: [Server]) -> Bool {
    // 类似火柴拼正方形的思路
    // 尝试将任务分配到服务器上
    // 如果某个服务器的负载超过容量，回溯尝试其他分配方式
}
```

### 2. 容器装箱问题

在物流系统中，我们可能需要将多个物品装到多个容器中，每个容器有固定的容量。我们可以用类似的回溯算法来找到最优的装箱方案。

```swift
// 伪代码示例
func packItems(_ items: [Item], _ containers: [Container]) -> Bool {
    // 类似火柴拼正方形的思路
    // 尝试将物品装到容器中
    // 如果某个容器的容量超过限制，回溯尝试其他装箱方式
}
```

### 3. 任务调度问题

在任务调度系统中，我们可能需要将多个任务分配到多个处理器上，每个处理器有固定的处理能力。我们可以用类似的回溯算法来找到最优的调度方案。

```swift
// 伪代码示例
func scheduleTasks(_ tasks: [Task], _ processors: [Processor]) -> Bool {
    // 类似火柴拼正方形的思路
    // 尝试将任务分配到处理器上
    // 如果某个处理器的负载超过能力，回溯尝试其他调度方式
}
```

### 4. 游戏开发中的应用

在一些拼图类游戏中，我们可能需要将多个拼图块拼成一个完整的图形。我们可以用类似的回溯算法来检查玩家是否能够完成拼图。

```swift
// 伪代码示例
func canCompletePuzzle(_ pieces: [PuzzlePiece], _ targetShape: Shape) -> Bool {
    // 类似火柴拼正方形的思路
    // 尝试将拼图块放到目标图形的不同位置
    // 如果某个位置放不下，回溯尝试其他位置
}
```

## 总结

这道题其实挺有代表性的，它展示了回溯算法在解决组合优化问题中的强大威力。通过合理的剪枝和优化，我们可以大大提高算法的效率。

**关键点总结：**

1. **基础判断很重要**：在开始回溯之前，先检查一些明显不可能的情况（比如总长度不能被 4 整除、有火柴长度超过目标长度等），可以大大减少不必要的计算。

2. **排序优化**：对火柴长度进行降序排序，可以让我们更快地发现不可能的情况，从而进行剪枝。

3. **避免重复计算**：利用对称性（四条边是对称的），避免重复计算相同的分配方式。

4. **回溯的核心**：尝试所有可能的分配方式，如果某条路径走不通，就回退到上一步，尝试其他路径。

5. **实际应用**：类似的思路在资源分配、容器装箱、任务调度等问题中都有应用。

虽然这道题的时间复杂度在最坏情况下是指数级的，但由于题目中 `matchsticks.length <= 15`，而且我们使用了多种优化技巧，实际运行时间还是可以接受的。在实际开发中，如果遇到类似的问题，我们可以根据具体情况调整算法，比如使用动态规划、贪心算法等其他方法。

希望这篇文章能帮助你理解回溯算法，以及如何在实际开发中应用类似的思路。如果你有什么问题或建议，欢迎留言讨论！

## 完整可运行 Demo 代码

下面是一个完整的可运行示例，包含了测试用例和详细的输出：

```swift
import Foundation

class Solution {
    func makesquare(_ matchsticks: [Int]) -> Bool {
        // 计算所有火柴的总长度
        let totalLength = matchsticks.reduce(0, +)
        
        // 如果总长度不能被 4 整除，肯定拼不成正方形
        guard totalLength % 4 == 0 else {
            return false
        }
        
        // 计算每条边的目标长度
        let targetLength = totalLength / 4
        
        // 如果任何一根火柴的长度超过目标长度，肯定拼不成
        if matchsticks.contains(where: { $0 > targetLength }) {
            return false
        }
        
        // 对火柴长度进行降序排序，这样可以更快地剪枝
        let sortedMatchsticks = matchsticks.sorted(by: >)
        
        // 初始化四条边的当前长度
        var sides = [0, 0, 0, 0]
        
        // 使用回溯算法尝试分配火柴
        return backtrack(sortedMatchsticks, 0, &sides, targetLength)
    }
    
    // 回溯函数
    private func backtrack(_ matchsticks: [Int], _ index: Int, _ sides: inout [Int], _ targetLength: Int) -> Bool {
        // 如果所有火柴都分配完了，检查是否每条边都等于目标长度
        if index == matchsticks.count {
            return sides.allSatisfy { $0 == targetLength }
        }
        
        let currentMatchstick = matchsticks[index]
        
        // 尝试将当前火柴放到四条边中的一条
        for i in 0..<4 {
            // 如果当前边加上这根火柴的长度超过目标长度，跳过（剪枝）
            if sides[i] + currentMatchstick > targetLength {
                continue
            }
            
            // 如果当前边和前面的边长度相同，跳过（避免重复计算）
            // 这是一个重要的优化，因为四条边是对称的
            if i > 0 && sides[i] == sides[i - 1] {
                continue
            }
            
            // 将当前火柴放到第 i 条边
            sides[i] += currentMatchstick
            
            // 递归尝试分配下一根火柴
            if backtrack(matchsticks, index + 1, &sides, targetLength) {
                return true
            }
            
            // 回溯：撤销刚才的操作
            sides[i] -= currentMatchstick
        }
        
        // 如果所有尝试都失败了，返回 false
        return false
    }
}

// 测试用例
func testSolution() {
    let solution = Solution()
    
    // 测试用例 1
    let test1 = [1,1,2,2,2]
    let result1 = solution.makesquare(test1)
    print("测试用例 1: \(test1)")
    print("结果: \(result1)")
    print("预期: true")
    print("---")
    
    // 测试用例 2
    let test2 = [3,3,3,3,4]
    let result2 = solution.makesquare(test2)
    print("测试用例 2: \(test2)")
    print("结果: \(result2)")
    print("预期: false")
    print("---")
    
    // 测试用例 3
    let test3 = [5,5,5,5,4,4,4,4,3,3,3,3]
    let result3 = solution.makesquare(test3)
    print("测试用例 3: \(test3)")
    print("结果: \(result3)")
    print("预期: true")
    print("---")
    
    // 测试用例 4
    let test4 = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
    let result4 = solution.makesquare(test4)
    print("测试用例 4: \(test4)")
    print("结果: \(result4)")
    print("预期: false")
    print("---")
    
    // 测试用例 5
    let test5 = [1,1,1,1]
    let result5 = solution.makesquare(test5)
    print("测试用例 5: \(test5)")
    print("结果: \(result5)")
    print("预期: true")
    print("---")
}

// 运行测试
testSolution()
```

**运行结果：**

```
测试用例 1: [1, 1, 2, 2, 2]
结果: true
预期: true
---
测试用例 2: [3, 3, 3, 3, 4]
结果: false
预期: false
---
测试用例 3: [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]
结果: true
预期: true
---
测试用例 4: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
结果: false
预期: false
---
测试用例 5: [1, 1, 1, 1]
结果: true
预期: true
---
```

这个 Demo 代码可以直接在 Xcode 或 Swift Playground 中运行，你可以修改测试用例来验证算法的正确性。


这道题其实挺有意思的，它让我们用一堆长度不同的火柴棒，看看能不能拼成一个完整的正方形。听起来简单，但实际做起来还是需要一些技巧的。我们需要用回溯算法，尝试把每根火柴放到正方形的四条边中的一条，看看能不能正好填满。今天我们就用 Swift 来搞定这道题，顺便聊聊它在实际开发中能用到哪些场景。

LeetCode 473 火柴拼正方形

全栈

编程语言

算法

客户端

学习如何用Swift实现火柴拼正方形算法，掌握回溯算法核心思想及优化技巧。通过降序排序、剪枝等策略高效解决问题，适用于资源分配、装箱问题等实际场景。包含完整代码示例和测试用例分析。

游戏开发

服务器

容器

Swift

Xcode

2026新春采购季

4核4G3M云服务器 新用户低至38元/年！

tcap

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

LeetCode 473 火柴拼正方形-腾讯云开发者社区-腾讯云

LeetCode 473 火柴拼正方形

LeetCode 473 火柴拼正方形

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐