473. Matchsticks to Square - Explanation

Description

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

Example 1:

Input: matchsticks = [1,3,4,2,2,4]

Output: true

Example 2:

Input: matchsticks = [1,5,6,3]

Output: false

Constraints:

1 <= matchsticks.length <= 15.
1 <= matchsticks[i] <= 100,000,000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Backtracking (Brute Force)

Intuition

To form a square, we need to partition matchsticks into 4 groups with equal sums. Each matchstick must be assigned to exactly one side. We try placing each matchstick on each of the 4 sides recursively. If we successfully place all matchsticks and all 4 sides have equal length, we found a valid square.

Algorithm

Calculate the total length. If not divisible by 4, return false immediately.
Create an array sides of size 4 to track the current length of each side.
Use backtracking: for each matchstick, try adding it to each of the 4 sides.
After placing a matchstick, recurse to place the next one.
If we place all matchsticks and all sides are equal, return true.
Backtrack by removing the matchstick from the current side before trying the next side.

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        if sum(matchsticks) % 4 != 0:
            return False

        sides = [0] * 4

        def dfs(i):
            if i == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == sides[3]

            for side in range(4):
                sides[side] += matchsticks[i]
                if dfs(i + 1):
                    return True
                sides[side] -= matchsticks[i]

            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O(4 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Backtracking (Pruning)

Intuition

The brute force approach explores many redundant paths. We can prune significantly with two optimizations. First, sort matchsticks in descending order so larger sticks are placed first, failing faster when a configuration is impossible. Second, skip trying to place a matchstick on an empty side if we already tried another empty side, since empty sides are interchangeable.

Algorithm

Calculate the total length and target side length. Return false if total is not divisible by 4.
Sort matchsticks in descending order for early pruning.
In the recursive function, try placing the current matchstick on each side:
- Skip if adding the matchstick would exceed the target length.
- If placement succeeds recursively, return true.
- Backtrack by removing the matchstick.
- If the current side is empty after backtracking, stop trying other sides (they are equivalent).
Return true if all matchsticks are placed successfully.

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)
        if total_length % 4 != 0:
            return False

        length = total_length // 4
        sides = [0] * 4
        matchsticks.sort(reverse=True)

        def dfs(i):
            if i == len(matchsticks):
                return True

            for side in range(4):
                if sides[side] + matchsticks[i] <= length:
                    sides[side] += matchsticks[i]
                    if dfs(i + 1):
                        return True
                    sides[side] -= matchsticks[i]

                if sides[side] == 0:
                    break

            return False

        return dfs(0)

Time & Space Complexity

Time complexity: $O(4 ^ n)$
Space complexity: $O(n)$ for recursion stack.

3. Dynamic Programming (Bit Mask)

Intuition

We can represent which matchsticks have been used with a bitmask. For each subset of matchsticks, we track the current "partial side" length (sum modulo target side length). If we can use all matchsticks such that each completed side reaches exactly the target length, we have a valid square. Memoization avoids recomputing results for the same subset.

Algorithm

Validate that the total length is divisible by 4 and no single matchstick exceeds the target side length.
Sort matchsticks in descending order for better pruning.
Use a DP array where dp[mask] stores the partial sum of the current incomplete side for that subset of used matchsticks.
Starting from the full bitmask, recursively try removing each matchstick:
- If the resulting partial sum plus the matchstick does not exceed the target, update dp[mask].
- Use modulo to reset when a side is completed.
Return true if dp[fullMask] == 0, meaning all sides completed perfectly.

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total_length = sum(matchsticks)
        if total_length % 4 != 0:
            return False

        length = total_length // 4
        if max(matchsticks) > length:
            return False

        n = len(matchsticks)
        dp = [float("-inf")] * (1 << n)
        matchsticks.sort(reverse=True)

        def dfs(mask):
            if mask == 0:
                return 0
            if dp[mask] != float("-inf"):
                return dp[mask]

            for i in range(n):
                if mask & (1 << i):
                    res = dfs(mask ^ (1 << i))
                    if res >= 0 and res + matchsticks[i] <= length:
                        dp[mask] = (res + matchsticks[i]) % length
                        return dp[mask]
                    if mask == (1 << n) - 1:
                        dp[mask] = -1
                        return -1

            dp[mask] = -1
            return -1

        return not dfs((1 << n) - 1)

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity: $O(n + 2 ^ n)$

Common Pitfalls

Not Checking If Total Length Is Divisible by 4

Before attempting any backtracking, verify that the total sum of matchsticks is divisible by 4. Without this early check, the algorithm wastes time exploring configurations that can never form a valid square.

Missing the Single Matchstick Length Check

If any single matchstick is longer than the target side length (total / 4), it is impossible to form a square. Failing to check this upfront leads to unnecessary recursion and potential timeout.

Not Sorting Matchsticks in Descending Order

Sorting matchsticks in descending order significantly improves pruning efficiency. Placing larger matchsticks first causes invalid configurations to fail faster, reducing the search space dramatically. Without sorting, the algorithm may explore many more branches.

Redundant Exploration of Empty Sides

When backtracking, if placing a matchstick on an empty side fails, there is no need to try other empty sides since they are equivalent. Breaking out of the loop when sides[i] == 0 after backtracking prevents exploring symmetric, redundant configurations.

Integer Overflow in Bitmask DP

When using bitmask DP, ensure the DP array size (1 << n) does not cause integer overflow. For n up to 15, this creates arrays of size 32768, which is manageable, but larger values can cause memory issues.