Show problems as
Classic problem #473MediumArrayDynamic ProgrammingBacktrackingBit ManipulationBitmask

Matchsticks to Square

Real-world version: Fencing a Square From Every Rod
Tracked in this browser only
Read Matchsticks to Square on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A pile of rods has the lengths rods. Every rod has to be used exactly once, laid end to end without being broken or bent, and the rods must be grouped into the four sides of a square.

Return whether that is possible.

Examples

Example 1

Input
rods = [5, 5, 5, 5, 4, 4, 4, 4]
Output
true

The lengths add to thirty-six, so each side must come to nine, which is one rod of 5 laid with one rod of 4. There are four of each, so the four sides come out alike.

Example 2

Input
rods = [4, 4, 3, 3, 3, 3]
Output
false

The lengths add to twenty, so each side must come to five. No group of these rods comes to five: a 4 leaves one over and nothing is that short, a 3 leaves two over and nothing is that short either.

Example 3

Input
rods = [1, 2, 3, 4, 5]
Output
false

The lengths add to fifteen, which does not divide evenly by four, so no square is possible whatever the arrangement.

Constraints

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

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def makesquare(rods: list[int]) -> bool:
Java
public boolean makesquare(int[] rods)

More on the same topics