LeetCode 473: Matchsticks to Square Solution in Python – A Step-by-Step Guide

What Is LeetCode 473: Matchsticks to Square?

In LeetCode 473: Matchsticks to Square, you’re given an array matchsticks of integer lengths, and your task is to determine if you can use all the matchsticks to form a square—four sides of equal length. Each matchstick must be used exactly once, and the total length must divide evenly into 4. For example, with [1, 1, 2, 2, 2], total 8 divides into 4 sides of 2, and it’s possible; but [1, 1, 1, 1, 5] (total 9) can’t form a square (9/4 = 2.25, not integer). It’s like assembling a square frame from a quirky set of sticks.

Problem Statement

• Input: matchsticks (List[int])—array of matchstick lengths.
• Output: bool—True if a square can be formed, False otherwise.
• Rules:
• Use all matchsticks exactly once.
• Form 4 equal-length sides.
• Sum of lengths must be divisible by 4.

Constraints

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

Examples to Get Us Started

• Input: matchsticks = [1,1,2,2,2]
• Output: True (Sides: 1+1, 2, 2, 2 = 2 each).
• Input: matchsticks = [3,3,3,3,4]
• Output: False (Total 16, sides 4, but 4 can’t split evenly).
• Input: matchsticks = [1,1,1,1]
• Output: True (Sides: 1 each).

Understanding the Problem: Crafting the Frame

To solve LeetCode 473: Matchsticks to Square in Python, we need to check if the total length of matchsticks divides into 4 equal parts and if the sticks can be grouped into four subsets with that sum. A naive approach—trying all partitions—could be O(4^n), infeasible for n = 15. The key? Use backtracking with pruning to efficiently test combinations. We’ll explore:

• Best Solution (Backtracking with Pruning): O(4^n) worst-case, O(n) space—fast with optimizations.
• Alternative Solution (Brute Force Subset Generation): O(2^n) time, O(n)—simpler but slower.

Let’s dive into the backtracking solution—it’s the craftsman’s precise toolkit we need.

Best Solution: Backtracking with Pruning

Why This Is the Best Solution

The backtracking with pruning approach is the top pick because it’s O(4^n) worst-case time but significantly faster in practice with optimizations, using O(n) space. It sorts the array, checks divisibility, and recursively assigns matchsticks to four sides, pruning branches with early failures or descending order for efficiency. It’s like building a square frame piece-by-piece, backtracking when a fit fails—clever and optimized!

How It Works

Here’s the strategy:

• Step 1: Check base cases:
• Sum % 4 ≠ 0 or n < 4, return False.
• Step 2: Sort matchsticks in descending order (prune faster).
• Step 3: Backtrack:
• Target = sum / 4.
• Assign each matchstick to one of 4 sides (sums array).
• If side > target, skip.
• Recurse until all used or fail.
• Step 4: Return True if all sides equal target.
• Why It Works:
• Pruning reduces search space (large sticks first).
• Backtracking explores all valid partitions.

Step-by-Step Example

Example: matchsticks = [1,1,2,2,2]

• Sum: 8, target = 8/4 = 2, n = 5 ≥ 4.
• Sort: [2,2,2,1,1].
• Backtrack:
• Start: sums = [0,0,0,0].
• 2: sums[0] = 2, [2,0,0,0].
• 2: sums[1] = 2, [2,2,0,0].
• 2: sums[2] = 2, [2,2,2,0].
• 1: sums[3] = 1, [2,2,2,1].
• 1: sums[3] = 2, [2,2,2,2].
• All 2: True.

Example: matchsticks = [3,3,3,3,4]

• Sum: 16, target = 4.
• Sort: [4,3,3,3,3].
• Backtrack:
• 4: sums[0] = 4, [4,0,0,0].
• 3: sums[1] = 3, [4,3,0,0].
• 3: sums[2] = 3, [4,3,3,0].
• 3: sums[3] = 3, [4,3,3,3].
• 3: No fit (all > 1), backtrack fails.
• Result: False.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down clearly:

Copy codeclass Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        # Step 1: Base cases
        if not matchsticks or len(matchsticks) < 4:
            return False
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        target = total // 4

        # Step 2: Sort descending
        matchsticks.sort(reverse=True)
        if matchsticks[0] > target:
            return False

        # Step 3: Backtrack
        sums = [0] * 4
        def backtrack(index):
            if index == len(matchsticks):
                return sums[0] == sums[1] == sums[2] == sums[3] == target

            for i in range(4):
                if sums[i] + matchsticks[index] <= target:
                    sums[i] += matchsticks[index]
                    if backtrack(index + 1):
                        return True
                    sums[i] -= matchsticks[index]
                    # Prune: if this side failed at 0, skip others
                    if sums[i] == 0:
                        break
            return False

        return backtrack(0)

• Line 4-10: Check n < 4, sum % 4, compute target.
• Line 13-15: Sort descending, prune if max > target.
• Line 18-31: Backtrack:
• Base case: all used, check sums.
• Try each side, prune if > target.
• Recurse, backtrack if fails, optimize with zero check.
• Line 33: Start backtracking.
• Time Complexity: O(4^n)—worst-case, pruned in practice.
• Space Complexity: O(n)—recursion stack.

It’s like a matchstick frame builder!

Alternative Solution: Brute Force Subset Generation

Why an Alternative Approach?

The brute force subset generation checks all partitions—O(2^n) time, O(n) space—generating subsets and verifying four equal sums. It’s slow but intuitive, like trying every possible stick pile. Good for small n or learning!

How It Works

• Step 1: Generate all subsets.
• Step 2: Filter for 4 subsets with equal sums.
• Step 3: Check if all matchsticks used.

Step-by-Step Example

Example: matchsticks = [1,1,2]

• Sum: 4, target = 1 (but n < 4, False).
• Subsets: Too few for 4 equal parts.

Code for Brute Force (Simplified)

Copy codeclass Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        if len(matchsticks) < 4:
            return False
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        target = total // 4

        def can_partition(nums, k, target, used, curr_sum):
            if k == 0:
                return True
            if curr_sum == target:
                return can_partition(nums, k-1, target, used, 0)
            for i in range(len(nums)):
                if not used[i] and curr_sum + nums[i] <= target:
                    used[i] = True
                    if can_partition(nums, k, target, used, curr_sum + nums[i]):
                        return True
                    used[i] = False
            return False

        used = [False] * len(matchsticks)
        return can_partition(matchsticks, 4, target, used, 0)

• Time Complexity: O(2^n)—subset exploration.
• Space Complexity: O(n)—used array.

It’s a slow stick sorter!

Comparing the Two Solutions

• Backtracking (Best):
• Pros: O(4^n) worst, faster with pruning.
• Cons: O(n) space.
• Brute Force (Alternative):
• Pros: O(2^n), simpler concept.
• Cons: Slower, no pruning.

Backtracking wins for efficiency.

Edge Cases and Examples

• Input: [1] → False.
• Input: [1,1,1] → False.
• Input: [2,2,2,2] → True.

Backtracking handles all well.

Complexity Recap

• Backtracking: Time O(4^n) worst, Space O(n).
• Brute Force: Time O(2^n), Space O(n).

Backtracking’s the champ.

Key Takeaways

• Backtracking: Prune for speed.
• Brute Force: Check all piles.
• Python Tip: Sorting optimizes—see [Python Basics](/python/basics).

Final Thoughts: Build That Square

LeetCode 473: Matchsticks to Square in Python is a matchstick crafting adventure. Backtracking with pruning is your fast builder, while brute force is a slow assembler. Want more partitioning? Try LeetCode 416: Partition Equal Subset Sum or LeetCode 698: Partition to K Equal Sum Subsets. Ready to shape some sticks? Head to Solve LeetCode 473 on LeetCode and craft it today—your coding skills are square-ready!