Matchsticks to Square

Hard

You are given an array nums where nums[i] is the length of the i-th matchstick. You must use every matchstick exactly once, joining them (without breaking any) to form a square. Return true if you can form a square, otherwise false.

Example 1

Input:  matchsticks = [1,1,2,2,2]
Output: true
Explanation: Sides of length 2: {2},{2},{2},{1,1}.

Example 2

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

Constraints

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