Matchsticks to Square
Medium · Backtracking · Array · Dynamic Programming · Backtracking · Bit Manipulation · Bitmask
Problem
You are given an integer array matchsticks, where matchsticks[i] is the length of the i-th matchstick. Decide whether you can arrange all of the matchsticks into the outline of a square.
Each matchstick must be used exactly once and cannot be broken, though several matchsticks may be laid end to end along one side. Return true if a square can be formed and false otherwise.
Examples
Input: matchsticks = [1,3,2,2,4,2,2] Output: true
The total is 16, and the sides 4, 1+3, 2+2 and 2+2 each have length 4.
Input: matchsticks = [2,2,2,3,3,4] Output: false
Each side must be 4, but a side holding a 3 would need a 1, and there is none.
Input: matchsticks = [5,5,5,5] Output: true
One stick per side.
Constraints
- 1 <= len(matchsticks) <= 15
- 1 <= matchsticks[i] <= 10^8
Approaches
- Backtracking: longest stick first onto four sides — time O(4^n) worst case, space O(n)
Follow-up
What if the outline only had to be a rectangle? Then the sides are not known in advance; split the sticks into two groups that can each be halved (see the use case “A rectangle instead of a square”).
Related problems
Start free on Cariara · Coding problems · System design studio
