mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 01:15:57 +08:00
94 lines
3.0 KiB
Markdown
94 lines
3.0 KiB
Markdown
# [473. Matchsticks to Square](https://leetcode.com/problems/matchsticks-to-square/)
|
||
|
||
|
||
## 题目
|
||
|
||
You are given an integer array `matchsticks` where `matchsticks[i]` is the length of the `ith` matchstick. You want to use **all the matchsticks** to make one square. You **should not break** any stick, but you can link them up, and each matchstick must be used **exactly one time**.
|
||
|
||
Return `true` if you can make this square and `false` otherwise.
|
||
|
||
**Example 1:**
|
||
|
||
|
||
|
||
```
|
||
Input: matchsticks = [1,1,2,2,2]
|
||
Output: true
|
||
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: matchsticks = [3,3,3,3,4]
|
||
Output: false
|
||
Explanation: You cannot find a way to form a square with all the matchsticks.
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- `1 <= matchsticks.length <= 15`
|
||
- `0 <= matchsticks[i] <= 109`
|
||
|
||
## 题目大意
|
||
|
||
现在已知小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
|
||
|
||
## 解题思路
|
||
|
||
- 将火柴拼成一个正方形，可以将它们分成四组，每一根火柴恰好属于其中的一组；并且每一组火柴的长度之和都相同，等于所有火柴长度之和的四分之一。
|
||
- 考虑暴力解法，使用深度优先搜索枚举出所有的分组情况，并对于每一种情况，判断是否满足上述的两个条件(每根火柴属于其中一组，每组火柴长度之和相同)。依次对每一根火柴进行搜索，当搜索到第 i 根火柴时，可以考虑把它放到四组中的任意一种。对于每一种放置方法，继续对第 i + 1 根火柴进行深搜。当我们搜索完全部的 N 根火柴后，再判断每一组火柴的长度之和是否都相同。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
import "sort"
|
||
|
||
func makesquare(matchsticks []int) bool {
|
||
if len(matchsticks) < 4 {
|
||
return false
|
||
}
|
||
total := 0
|
||
for _, v := range matchsticks {
|
||
total += v
|
||
}
|
||
if total%4 != 0 {
|
||
return false
|
||
}
|
||
sort.Slice(matchsticks, func(i, j int) bool {
|
||
return matchsticks[i] > matchsticks[j]
|
||
})
|
||
visited := make([]bool, 16)
|
||
return dfs(matchsticks, 0, 0, 0, total, &visited)
|
||
}
|
||
|
||
func dfs(matchsticks []int, cur, group, sum, total int, visited *[]bool) bool {
|
||
if group == 4 {
|
||
return true
|
||
}
|
||
if sum > total/4 {
|
||
return false
|
||
}
|
||
if sum == total/4 {
|
||
return dfs(matchsticks, 0, group+1, 0, total, visited)
|
||
}
|
||
last := -1
|
||
for i := cur; i < len(matchsticks); i++ {
|
||
if (*visited)[i] {
|
||
continue
|
||
}
|
||
if last == matchsticks[i] {
|
||
continue
|
||
}
|
||
(*visited)[i] = true
|
||
last = matchsticks[i]
|
||
if dfs(matchsticks, i+1, group, sum+matchsticks[i], total, visited) {
|
||
return true
|
||
}
|
||
(*visited)[i] = false
|
||
}
|
||
return false
|
||
}
|
||
``` |