What is the primary approach to solve the Matchsticks to Square problem?

The primary approach is state transition dynamic programming, which efficiently handles the combinatorial nature of the problem using bitmasking.

How does pruning help with backtracking in this problem?

Pruning eliminates paths where forming a square is impossible, reducing the number of recursive calls and speeding up the process.

What is the time complexity of the solution?

The time complexity is O(N × 2^N), where N is the number of matchsticks.

How can bitmasking optimize the solution?

Bitmasking allows efficient representation and checking of subsets of matchsticks, speeding up state transitions during the backtracking process.

What is the key to solving the problem efficiently?

The key is using dynamic programming with bitmasking to reduce the complexity of tracking which matchsticks are used and where to place them.

#473

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

火柴拼正方形

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次。如果你能使这个正方形，则返回 true ，否则返回 false …

数组动态规划回溯位运算位掩码

题目描述

你将得到一个整数数组 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⁸

lightbulb

解题思路

方法一：排序 + 回溯

用 $edges[i]$ 记录正方形每条边当前的长度，对于第 $u$ 根火柴，尝试把它加到 $edges[i]$ 每条边，若加入后 $edges[i]$ 不超过正方形期望长度 $x$ ，则继续往下递归 $u+1$ 根火柴。若所有火柴都能被加入，说明满足拼成正方形的要求。

这里对 $matchsticks$ 从大到小排序，可以减少搜索次数。

时间复杂度 $O(4^n)$ ，其中 $n$ 表示 $matchsticks$ 的长度。每根火柴可以被放入正方形的 $4$ 条边，共有 $n$ 根火柴。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        def dfs(u):
            if u == len(matchsticks):
                return True
            for i in range(4):
                if i > 0 and edges[i - 1] == edges[i]:
                    continue
                edges[i] += matchsticks[u]
                if edges[i] <= x and dfs(u + 1):
                    return True
                edges[i] -= matchsticks[u]
            return False

        x, mod = divmod(sum(matchsticks), 4)
        if mod or x < max(matchsticks):
            return False
        edges = [0] * 4
        matchsticks.sort(reverse=True)
        return dfs(0)

speed

复杂度分析

指标	值
时间	O(N \times 2^N)
空间	O(N + 2^N)

psychology

面试官常问的追问

外企场景

question_mark
Ability to identify the state transition dynamic programming approach.
question_mark
Skill in applying backtracking and pruning to reduce search space.
question_mark
Familiarity with bitmasking for optimizing combinatorial problems.

warning

常见陷阱

外企场景

error
Not considering the pruning step, leading to unnecessary recursion.
error
Misunderstanding the problem as needing to partition into 3 parts instead of 4.
error
Inefficient state representation, which can result in slow performance for larger inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the matchsticks had to form a rectangle instead of a square?
arrow_right_alt
How would the problem change if we were given a fixed perimeter for the square?
arrow_right_alt
What if we needed to divide the matchsticks into multiple squares instead of just one?

help

常见问题

外企场景

继续练习

#526 优美的排列 #638 大礼包 #691 贴纸拼词