Can every matchstick, used once and unbroken, form a square? Check the total splits by four, sort longest first, then place each stick on a side with room and undo on a dead end, skipping side lengths already tried.
▼The problem
LeetCode 473 (Medium). Given the lengths of some matchsticks, decide whether all of them, each used exactly once and none broken, can form a square.
Examples (LeetCode's): [1,1,2,2,2] → true (total 8, side 2: three twos, and the two ones end to end make the fourth side; scenes 2 and 7); [3,3,3,3,4] → false (scene 8).
The solution
def makesquare(sticks):
side, rem = divmod(sum(sticks), 4)
sticks.sort(reverse=True)
if rem or sticks[0] > side:
return False
sides = [0] * 4
def place(i):
if i == len(sticks):
return True
tried = set()
for s in range(4):
if sides[s] + sticks[i] > side or sides[s] in tried:
continue
tried.add(sides[s])
sides[s] += sticks[i]
if place(i + 1):
return True
sides[s] -= sticks[i]
return False
return place(0)Transcript
Matchsticks to Square. Use every matchstick exactly once, without breaking any, and decide whether they form a square.
Take one, one, two, two, two. The total is eight, so each side is two: three twos, plus the two ones end to end. True.
The naive way tries every stick on every side: four to the n assignments. Over a thousand for five sticks, over a billion for fifteen.
Instead, backtrack and prune. If the total isn't divisible by four, or a stick is longer than a side, stop. Otherwise, sort longest first, so dead ends show up early. Place each stick on a side with room, never overflowing, and when a choice fails, undo it. And skip any side whose length was already tried: identical sides, identical searches.
In code: check the total, sort, and recurse stick by stick, with a set of lengths already tried. When every stick is placed, it's a square.
Walking the first example: the twos fill three sides, and both ones land on the last. True.
Now three, three, three, three, four. Each side is four, and the four fits: no early exit. The four fills a side, and the threes start the other three. The last three fits nowhere. Undo. Every other side has a length already tried, so pruning skips them, all the way up. False, after four placements. Without the skip, sixty-four.
Worst case, it's still order four to the n time and order n space, but pruning makes it fast in practice.
Sort, place, prune. That's Matchsticks to Square.