Matchsticks to Square

LeetCode 473 | Difficulty: Medium

Medium

Problem Description

You are given an integer array 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.

Example 1:

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.

Example 2:

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`

Topics: Array, Dynamic Programming, Backtracking, Bit Manipulation, Bitmask

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Backtracking

Explore all candidates by building solutions incrementally. At each step, choose an option, explore further, then unchoose (backtrack) to try the next option. Prune branches that can't lead to valid solutions.

When to use

Generate all combinations/permutations, or find solutions that satisfy constraints.

Bit Manipulation

Operate directly on binary representations. Key operations: AND (&), OR (|), XOR (^), NOT (~), shifts (<<, >>). XOR is especially useful: a ^ a = 0, a ^ 0 = a.

When to use

Finding unique elements, power of 2 checks, subset generation, toggling flags.

---

Solutions

Solution 1: C# (Best: 136 ms)

Metric	Value
Runtime	136 ms
Memory	38.6 MB
Date	2022-02-04

Solution

public class Solution {
    public bool Makesquare(int[] matchsticks) {
       int n = matchsticks.Length;
    int sum = matchsticks.Sum();
    if (sum % 4 != 0 || n < 4) return false;
    int[] sides = new int[4];
    int target = sum / 4;
    Array.Sort(matchsticks, (a, b) => { return b - a; });
    return MakesSquareDfs(matchsticks, sides, 0, target);
}

bool MakesSquareDfs(int[] matches, int[] sides, int index, int target)
{
    if(index == matches.Length)
    {
        return sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3];
    }
    for (int i = 0; i < 4; i++)
    {
        if(sides[i]+matches[index] > target) continue;
        int j = i;
        while(--j>=0)
        {
            if(sides[i] == sides[j]) break;
        }
        if(j != -1) continue;
        sides[i] += matches[index];
        if(MakesSquareDfs(matches, sides, index+1, target))
        return true;
        sides[i] -= matches[index];
    }
    return false;
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$
Backtracking	$O(n! or 2^n)$	$O(n)$
Bit Manipulation	$O(n) or O(1)$	$O(1)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• Identify pruning conditions early to avoid exploring invalid branches.
• LeetCode provides 5 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Treat the matchsticks as an array. Can we split the array into 4 equal parts?

Hint 2: Every matchstick can belong to either of the 4 sides. We don't know which one. Maybe try out all options!

Hint 3: For every matchstick, we have to try out each of the 4 options i.e. which side it can belong to. We can make use of recursion for this.

Hint 4: We don't really need to keep track of which matchsticks belong to a particular side during recursion. We just need to keep track of the length of each of the 4 sides.

Hint 5: When all matchsticks have been used we simply need to see the length of all 4 sides. If they're equal, we have a square on our hands!