Abstract / Summary

Determine if given matchstick lengths can form a square using all pieces without breaking any.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 42% (500k+ submissions).

Typical patterns to solve this problem:

• Array
• Backtracking
• Bit Manipulation
• Bitmask
• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation decides whether a collection of matchsticks can be arranged to form a perfect square. It first eliminates impossible configurations through simple arithmetic checks, then incrementally builds candidate side length distributions while pruning infeasible branches. The algorithm returns a Boolean indicating the existence of a valid arrangement.

Key Steps

Sorting and early rejection

matchsticks.sort(reverse=True)

s = sum(matchsticks)
if s % 4 != 0:
    return False

Sorting the sticks in descending order places the longest sticks first, which helps the later search to fail fast when a large stick cannot fit. The total length must be divisible by four; otherwise a square is impossible.

Determining side length and maximum-stick check

side = s // 4
if max(matchsticks) > side:
    return False

The target length of each side is computed. If any single stick exceeds this target, no arrangement can succeed, so the function returns early.

Initial state preparation

last = min(matchsticks)

all = [[matchsticks[0], 0, 0, 0]]
del matchsticks[0]

last records the smallest stick, which is later used as a pruning threshold. The algorithm starts with a single partial configuration where the first (largest) stick occupies the first side, and the remaining three sides are empty.

Iterative construction of side combinations

for stick in matchsticks:
    next = []
    for current in all:
        for pos in range(4):
            current[pos] += stick
            gap = side - current[pos]
            if gap >= 0:
                s = sorted(current)
                if (gap == 0 or gap >= last) and s not in next:
                    next.append(s)
            current[pos] -= stick
    all = next

For each remaining stick, the algorithm attempts to place it on each of the four sides of every currently viable configuration. After a tentative addition, it computes the remaining length (gap) needed to complete that side. If the gap is non-negative, the configuration is sorted to a canonical form, which enables duplicate detection. The condition gap == 0 or gap >= last ensures that a side is either completed exactly or still has enough room to accommodate the smallest remaining stick, preventing dead-end branches. Only unique configurations survive to the next iteration.

Final decision

return len(all) > 0

If at least one configuration remains after processing all sticks, a square can be formed; otherwise, it cannot.

Edge Cases Handled

The code explicitly guards against three fundamental impossibilities. First, when the total length of all sticks is not a multiple of four, the modulo check rejects the input immediately. Second, if any individual stick is longer than the computed side length, the maximum-stick check eliminates the case. Third, during the iterative placement, the condition gap >= last prevents the algorithm from pursuing a partial side that would be impossible to finish because the smallest remaining stick would already exceed the remaining gap. This effectively handles scenarios where a side is left with a gap smaller than any stick left to place.

Performance Optimizations

Sorting the matchsticks in descending order is a classic heuristic that brings larger constraints to the front, causing early failures for infeasible branches. The early arithmetic checks (s % 4 and max(matchsticks) > side) prune the search space before any recursion or iteration begins. Within the main loop, the algorithm stores configurations in a canonical sorted form, allowing a simple containment test (s not in next) to avoid duplicate work without resorting to more complex data structures. The additional pruning rule that a side’s remaining gap must be at least the smallest stick (gap >= last) discards branches that cannot possibly be completed, reducing the number of configurations that need to be examined. By iteratively rebuilding the all list rather than using recursion, the implementation avoids the overhead of deep call stacks and leverages Python’s list handling for batch updates.

Imagine you have a bunch of wooden sticks of different lengths and you want to put them together to build a perfect square. A square has four sides that are all exactly the same size.

First, the code checks if the total length of all the sticks can actually make a square. If you add up the lengths of all the sticks and the total cannot be divided into four equal parts, it is impossible to build the square, so the code says that it cannot be done. Also, if one single stick is already longer than what one side of the square should be, you cannot use it because it would make that side too big.

To build the square, the code organizes the sticks from longest to shortest to make it easier to handle. Then, it starts building the four sides at the same time. It takes each stick one by one and tries placing it on each of the four sides. As it adds a stick to a side, it checks to see if the total length of that side stays equal to or smaller than the target side length. If it fits, the code remembers how long that side is now and moves on to the next stick.

It keeps trying different combinations by adding the sticks to different sides. If a side ever gets to be exactly the right length, that part of the square is finished. If it finds a way to fill all four sides perfectly so that every stick is used and every side reaches the goal length, the puzzle is solved.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java	Python							TS
	WalkCCC	C++	Java	Python
	leetcode.ca	C++	Java	Python			Rust		Go
	LeetcodeHelp	C++	Java	Python
	Progiez	C++	Java	Python
github	black-shadows	C++
	charles-wangkai		Java
	everthis				JS
	fengvyi	C++
	fsq	C++
	gouthampradhan		Java
	halfrost								Go
	JoshCrozier				JS
	linouk23	C++
	lkwq007			Python
	martianoff					Scala
	ruoru						Rust
	suxrobGM									C#
	trung-hn			Python
	varunu28		Java
	vthwang		Java
	wisdompeak	C++
	yuanliu666							Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fengvyi	C++
fsq	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
martianoff	Scala
ruoru	Rust
suxrobGM	C#
trung-hn	Python
varunu28	Java
vthwang	Java
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality