377. Matchsticks to Square
A pile of matchsticks sits in front of you, and the array matchsticks records each stick's length. You want to arrange all of them into the border of a square: every matchstick must be used exactly once, sticks may not be broken, and sticks laid end to end on the same edge simply add their lengths.
Return true if the sticks can form a square — four edges of identical total length — and false otherwise.
Example 1:
Input: matchsticks = [1, 1, 2, 2, 2]
Output: true
Explanation: The total length is 8, so each edge must measure 2. Three edges use a single stick of length 2, and the fourth chains the two sticks of length 1.
Example 2:
Input: matchsticks = [3, 3, 3, 3, 4]
Output: false
Explanation: The total is 16, so each edge would need length 4 — but the stick of length 4 forces the other four sticks of length 3 onto three edges, and 3 + 3 = 6 overshoots. No arrangement works.
Constraints:
- 1 ≤ matchsticks.length ≤ 15
- 1 ≤ matchsticks[i] ≤ 10⁸
Hints:
Two instant rejections: if the total length isn't divisible by 4 there is no square, and if any single stick is longer than total/4 it can't fit on any edge.
Try building the four edges by backtracking: assign each stick to one of the 4 edges and undo on failure. Sort the sticks in descending order first — big sticks fail fast — and never try two edges that currently have the same partial sum (they're interchangeable).
With n ≤ 15 you can also do subset DP: dp[mask] = "the sticks in mask can be arranged as some complete edges plus one partial edge". The partial edge's length is just sum(mask) mod (total/4), so each state needs only a boolean.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matchsticks = [1, 1, 2, 2, 2]
Expected output: true