613. Matchstick Square
A craft club has several sticks whose lengths are listed in sticks. The sticks may not be broken, but they can be glued end to end. The club wants to build a square frame that uses every stick exactly once, so each of the four sides is made of one or more whole sticks and all four sides have the same total length.
Return true if such a frame can be built and false otherwise. Trying every assignment of sticks to sides takes about 4^n steps; use the structure of the problem (side length is fixed, order inside a side does not matter) to bring this down to about 2^n * n.
Example 1
- Input:
- sticks = [3,3,3,3]
- Output:
- true
- Explanation:
Each side is a single stick of length 3.
Example 2
- Input:
- sticks = [1,2,3,4,5,5]
- Output:
- true
- Explanation:
The total is 20, so each side must be 5: sides
5,5,1 + 4and2 + 3.
Example 3
- Input:
- sticks = [2,2,2,3,3]
- Output:
- false
- Explanation:
The total is 12, so each side must be 3, but three sticks of length 2 cannot be combined into sums of 3.
Constraints
- 1 ≤
sticks.length≤ 15 - 1 ≤
sticks[i]≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(2^n * n)
- Space
- O(2^n)