All problems

Matchsticks to Square

Medium · backtracking

You are given a list matchsticks, where matchsticks[i] is the length of the i-th stick. You want to lay the sticks out as the four sides of a square. Every stick must be used exactly once, sticks cannot be broken, and a side may be made of several sticks placed end to end.

Return true if the four sides can all have the same length, and false otherwise.

Examples

Example 1

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

Output: true

Three sides use one stick of length 2 each, and the fourth side is the two sticks of length 1.

Example 2

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

Output: false

The total is 16, so each side would need length 4, but no way of grouping the sticks gives four sides of 4.

Example 3

Input: matchsticks = [1, 2, 3]

Output: false

The total is 6, which cannot be split into four equal sides.

Constraints