Matchsticks to Square Python Solution

Tested Python solution for LeetCode 473 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 473, Medium. Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

lcpy gen -n 473   # by problem number
lcpy gen -s matchsticks_to_square   # by problem name

​

Problem

You are given an integer array matchsticks where matchsticks[i] is the length of the ith 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.

​

Examples

Input: matchsticks = [1,1,2,2,2]
Output: true
Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Input: matchsticks = [3,3,3,3,4]
Output: false
Explanation: You cannot find a way to form a square with all the matchsticks.

​

Constraints

• 1 <= matchsticks.length <= 15
• 1 <= matchsticks[i] <= 10^8

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(4^n) backtracking in the worst case (pruned heavily in practice)
    # Space: O(n) recursion stack
    def makesquare(self, matchsticks: list[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        side = total // 4
        # Sort descending so larger sticks fail fast and prune the search early.
        sticks = sorted(matchsticks, reverse=True)
        if sticks[0] > side:
            return False
        sides = [0, 0, 0, 0]

        def backtrack(index: int) -> bool:
            if index == len(sticks):
                return all(s == side for s in sides)
            stick = sticks[index]
            for i in range(4):
                if sides[i] + stick > side:
                    continue
                # Skip duplicate side fills to avoid symmetric permutations.
                if i > 0 and sides[i] == sides[i - 1]:
                    continue
                sides[i] += stick
                if backtrack(index + 1):
                    return True
                sides[i] -= stick
            return False

        return backtrack(0)

​

Complexity

Time	Space
O(4^n) backtracking in the worst case (pruned heavily in practice)	O(n) recursion stack

​

Tags

NeetCode 250, NeetCode All.