MediumNo. 0473
Matchsticks to Square — LeetCode 473 Python Solution
- Pattern
- Backtracking
- Topics
- Bit Manipulation, Array, Dynamic Programming, Backtracking, Bitmask
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
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)Complexity
- Time
- O(n·m) (typical)
- Space · auxiliary
- O(n·m)or optimized
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 473. Matchsticks to Square is filed here because LeetCode tags it Backtracking, which is the vocabulary this hub collects.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0526 | Beautiful Arrangement | Medium |
| 0638 | Shopping Offers | Medium |
| 0698 | Partition to K Equal Sum Subsets | Medium |
| 1655 | Distribute Repeating Integers | Hard |
| 1723 | Find Minimum Time to Finish All Jobs | Hard |
| 1799 | Maximize Score After N Operations | Hard |
Frequently asked questions
- How hard is LeetCode 473. Matchsticks to Square?
LeetCode 473. Matchsticks to Square is rated Medium on LeetCode.
- What topics does LeetCode 473. Matchsticks to Square cover?
LeetCode 473. Matchsticks to Square is tagged Bit Manipulation, Array, Dynamic Programming, Backtracking and Bitmask on LeetCode.