hardBacktrackingPure DSA~38 min
Assemble a Square From Cable Segments
A field crew has cable segments of given lengths. They must use every segment, unbent, to form the four equal sides of a perfect square. Decide whether it is possible.
Problem
Given an array matchsticks where matchsticks[i] is the length of the i-th stick, use ALL sticks to form a square. Each stick must be used exactly once and cannot be broken. Return true if a square can be formed, false otherwise.
Input
An integer array matchsticks of length [1, 15]; each length in [1, 10^8].
Output
A boolean: whether all sticks tile into a square.
Constraints
- 1 <= matchsticks.length <= 15
- 1 <= matchsticks[i] <= 10^8
Examples
Example 1
Input
[1,1,2,2,2]
Output
true
Side length 2: sides are {2},{2},{2},{1,1}.
Example 2
Input
[3,3,3,3,4]
Output
false
Total 16 cannot be split into four sides of 4 using these lengths.