Matchsticks to Square

Determine if you can partition matchsticks into four equal-length sides.

backtracking dfs partition pruning side-length

You are given an integer array `nums` representing the lengths of matchsticks. You have to use **all** matchsticks exactly once to form a **square**. The matchsticks can be broken, but they cannot be bent or partially used. A square has four sides of equal length.

Write a function `can_make_square(nums)` that returns `True` if the matchsticks can be arranged to form a square, and `False` otherwise.

**Details:**
- The side length of the square, if possible, is `sum(nums) // 4`. This must be exact, so `sum(nums)` must be divisible by 4.
- No matchstick can be omitted; every length must be assigned to exactly one side.
- You may assign matchsticks to sides in any order. The order of matchsticks in `nums` does not matter.

You must implement the function from scratch; do not use any built-in functions that solve the problem directly.

Constraints

- `1 <= len(nums) <= 15`
- `1 <= nums[i] <= 10^9`
- The function must return a boolean.
- Time complexity: The problem is NP-complete, but with the given constraints a well-pruned backtracking solution will run within typical limits (about 2^15 states).

Example

>>> can_make_square([1,1,2,2,2])
True
>>> can_make_square([1,1,1,1])
True
>>> can_make_square([3,3,3,3,4])
False
>>> can_make_square([1,1,1,1,1])
False

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

First compute the total sum. If it's not divisible by 4, return False immediately. What is the target side length?

Sort the matchsticks in descending order to place long pieces early and reduce the search tree.

Use a recursive backtracking function that tries to place each matchstick into one of the four currently forming sides. Skip sides that already have the same current length as a previously tried side to avoid duplicate attempts.

A common pruning: if any matchstick is longer than the target side, it's impossible.

When a side is completely filled, reset its length to 0 and move on; the number of filled sides can be used as a termination condition.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.