Problem Statement in English

You’re given an array of matchsticks, where matchsticks[i] is the length of the i-th matchstick.

You want to use all the matchsticks to make one square.

You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Return true if you can make this square and false otherwise.

Approach

We’re just going to have to try all possibilities. But we can make some optimizations.

We can maintain an array of 4 elements, each representing the length of the side of the square.

We can sort the matchsticks in decreasing order and then try to put each matchstick in one of the 4 sides. Sorting in reverse allows us to cut out some branches of the search space early on.

Since every side must be used, we can model our dfs function so that it takes the index of the matchstick we’re trying to place. If we reach an index that is out of bounds, it means we’ve successfully placed all matchsticks and we can return true.

For every matchstick, we can try to place it in one of the 4 sides. If placing it in a side doesn’t exceed the target length, we can recursively call dfs for the next matchstick. If that returns true, we can return true as well. If not, we can backtrack and try placing the matchstick in another side.

In order to eliminate some duplicate branches, we can maintain a seen set that keeps track of the lengths of the sides we’ve already tried to place the current matchstick in. If we encounter a side length that we’ve already tried, we can skip it.

If we’ve tried placing the current matchstick in all 4 sides and none of them worked, we can return false.

But if we reach the end of the matchsticks array, it means we’ve successfully placed all matchsticks and we can return true.

And we’re done!

Solution in Python


class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        matchsticks.sort(reverse=True)
        total = sum(matchsticks)
        
        if total % 4:
            return False

        target = total // 4
        l = len(matchsticks)

        sides = [0,0,0,0]

        def dfs(i):
            if i >= l:
                return True
            
            v = matchsticks[i]

            seen = set()
            
            for j in range(4):
                if sides[j] not in seen and sides[j] + v <= target:
                    seen.add(sides[j])
                    sides[j]+=v

                    if dfs(i+1):
                        return True

                    sides[j]-=v

            return False

        return dfs(0)

Complexity

  • Time: $O(4^n)$
    Since we can try placing each matchstick in one of the 4 sides.

  • Space: $O(n)$
    Since we can have at most n recursive calls on the call stack, for n matchsticks.

Mistakes I Made

I also made a less efficient version which used a Counter to keep track of the lengths of the sides instead of an array. I also didn’t use a seen set to eliminate duplicate branches, which caused the algorithm to run much slower.

And we are done.