Matchsticks Into a Square
Problem
You have a set of matchsticks with integer lengths. Decide whether you can use every stick exactly once, without breaking any, to form the outline of a square. There are between 1 and 15 sticks and each length is between 1 and 10^8. Trying all 4^15 ways to assign sticks to sides is about a billion cases, so the search must prune aggressively.
Examples
Input: sticks = [1, 1, 2, 2, 2]
Output: True
Why: the sides are 2, 2, 2 and 1 + 1Input: sticks = [3, 3, 3, 3, 4]
Output: False
Why: the total, 16, would need sides of 4, and the four 3s cannot reach 4 without breakingInput: sticks = [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]
Output: True
Why: every side is 5 + 4 + 3Hints
0 / 3
Check the cheap facts first: the total must split into four equal sides, and no stick may be longer than one side.
Place sticks one at a time, trying each of the four sides, and undo the placement when the rest cannot be completed. Placing the longest sticks first makes dead ends show up near the top of the tree.
Two sides with the same current length are interchangeable, so if placing a stick on a side of length L failed, placing it on another side of length L will fail too. Skip it. This also stops the search from trying four identical empty sides.
Solution
The side length is fixed at the total divided by four, so the question is whether the sticks split into four groups with that sum. The search places one stick per level, trying every side that still has room, and backs out when the remaining sticks cannot be placed. Three prunes make it fast. The totals check and the longest-stick check reject impossible inputs before any search. Sorting from longest to shortest means big sticks, which have the fewest options, are placed first and conflicts are found early. And at each level, sides with the same current length are interchangeable, so each distinct length is tried only once, which removes the symmetric copies of every failed branch. When all sticks are placed every side is exactly full, since no side ever exceeds the side length and the sum is four side lengths. The worst case is still O(4^n), but the prunes cut the real search to a tiny fraction of it, and space is O(n) for the recursion.
def makes_square(sticks):
total = sum(sticks)
if len(sticks) < 4 or total % 4:
return False
side = total // 4
sticks = sorted(sticks, reverse=True) # hardest sticks first
if sticks[0] > side:
return False
sides = [0] * 4
def place(i):
if i == len(sticks):
return True # every side is exactly full
tried = set()
for s in range(4):
if sides[s] in tried or sides[s] + sticks[i] > side:
continue # same length as a side already tried
tried.add(sides[s])
sides[s] += sticks[i]
if place(i + 1):
return True
sides[s] -= sticks[i] # undo and try the next side
return False
return place(0)
print(makes_square([1, 1, 2, 2, 2])) # -> True
print(makes_square([3, 3, 3, 3, 4])) # -> False
print(makes_square([5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3])) # -> True
print(makes_square([1, 1, 1])) # -> FalseStuck on the idea rather than the code? Word Search & Pruning covers it.