Matchsticks to Square

The key idea

Each matchstick must land in exactly one of four sides, and every side must reach total / 4. Sort the sticks largest-first and place each one into a side that still has room, undoing a placement (backtracking) when a stick cannot be completed.

Problem

You are given an integer array matchsticks where matchsticks[i] is the length of the i-th matchstick. You want to use all the matchsticks to make one square. You should not break any stick, but you can link them, and each matchstick must be used exactly once.

Return true if you can make this square and false otherwise.

Constraints

1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 10^8

Examples

Input: matchsticks = [1,1,2,2,2] Output: true

Input: matchsticks = [3,3,3,3,4] Output: false

Complexity

Time: O(4^n) Space: O(n)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →