# Matchsticks to Square
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/matchsticks-to-square)
Canonical: https://scaleengineer.com/dsa/problems/matchsticks-to-square
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Bitmask](https://scaleengineer.com/dsa/patterns/bitmask)
**Data structures:** Array
**Companies:** [eBay](https://scaleengineer.com/companies/ebay), [PhonePe](https://scaleengineer.com/companies/phonepe)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/matchsticks-to-square/image0.jpg) 

**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] <= 108`

# Approaches
## Brute-force Backtracking
This approach uses a simple depth-first search (DFS) to explore all possible distributions of matchsticks into four sides. It tries to place each matchstick into one of the four sides of the square. If a placement leads to a dead end (a side becomes too long), it backtracks and tries a different placement.
**Time:** O(4^N), where N is the number of matchsticks. For each of the N matchsticks, we have 4 choices (placing it in one of the four sides). This leads to an exponential number of states. · **Space:** O(N), where N is the number of matchsticks. This space is used by the recursion stack.
**Pros:** Simple to understand and implement.; Correctly solves the problem for very small inputs.
**Cons:** Extremely inefficient due to its high time complexity.; Explores many redundant states.; Likely to result in a 'Time Limit Exceeded' error on most platforms for the given constraints.
### Explanation
The brute-force backtracking algorithm systematically explores every possible way to assign each matchstick to one of the four sides of the potential square. It's a straightforward translation of the problem statement into a recursive search.

We define a recursive function that takes the index of the current matchstick and an array representing the current lengths of the four sides. For each matchstick, we try to add it to each of the four sides. If adding the stick doesn't violate the side length constraint, we proceed with the next matchstick by making a recursive call. If a recursive call eventually leads to a solution, we return `true`. If a path doesn't work out, we backtrack by undoing the choice and trying the next available option.

```java
class Solution {
    public boolean makesquare(int[] matchsticks) {
        if (matchsticks == null || matchsticks.length < 4) {
            return false;
        }
        long perimeter = 0;
        for (int stick : matchsticks) {
            perimeter += stick;
        }
        if (perimeter % 4 != 0) {
            return false;
        }
        long side = perimeter / 4;
        for (int stick : matchsticks) {
            if (stick > side) {
                return false;
            }
        }
        return backtrack(matchsticks, 0, new long[4], side);
    }

    private boolean backtrack(int[] matchsticks, int index, long[] sides, long targetSide) {
        if (index == matchsticks.length) {
            return sides[0] == targetSide && sides[1] == targetSide && sides[2] == targetSide;
        }

        int currentMatchstick = matchsticks[index];
        for (int i = 0; i < 4; i++) {
            if (sides[i] + currentMatchstick <= targetSide) {
                sides[i] += currentMatchstick;
                if (backtrack(matchsticks, index + 1, sides, targetSide)) {
                    return true;
                }
                sides[i] -= currentMatchstick; // Backtrack
            }
        }
        return false;
    }
}
```
### Algorithm
- First, perform some initial checks. The total length of all matchsticks (perimeter) must be divisible by 4. If not, it's impossible to form a square, so return `false`. Calculate the required side length for the square, which is `perimeter / 4`.
- If any single matchstick is longer than the target side length, it's also impossible, so return `false`.
- Define a recursive backtracking function, say `backtrack(index, sides)`, where `index` is the index of the current matchstick being considered, and `sides` is an array of 4 elements representing the current lengths of the four sides being built.
- The base case for the recursion is when `index` reaches the end of the `matchsticks` array. This means all matchsticks have been placed. We then check if all four sides have the target length. If they do, we've found a valid solution, and we return `true`.
- In the recursive step, for the `matchstick` at the current `index`, we try to place it into each of the four sides one by one.
- For each side `i` from 0 to 3, if adding `matchsticks[index]` does not make the side `i` longer than the target side length, we add it to the side.
- Then, we make a recursive call `backtrack(index + 1, sides)` to place the next matchstick.
- If the recursive call returns `true`, it means a solution was found, so we propagate `true` up the call stack.
- If the recursive call returns `false`, we backtrack by removing the current matchstick from side `i` and try placing it on the next side.

## Dynamic Programming with Bitmasking
This approach reframes the problem as a partition problem and uses dynamic programming with bitmasking. The state of the DP is represented by a bitmask, where each bit corresponds to a matchstick. `dp[mask]` stores whether the subset of matchsticks represented by `mask` can be partitioned into one or more complete sides of the square. The final answer is found by checking the DP state for the mask representing all matchsticks.
**Time:** O(3^N). The outer loop runs `2^N` times. The inner loop iterates through all submasks of a given mask. The total number of iterations across all masks is `Σ (k=0 to N) C(N,k) * 2^k = (1+2)^N = 3^N`. · **Space:** O(2^N) to store the DP table `dp` and the precomputed `sums` array.
**Pros:** Provides a guaranteed time complexity that is better than the naive brute-force approach.; It's a systematic way to solve the partition problem, avoiding re-computation of results for the same subsets.
**Cons:** High space complexity of O(2^N) can be a problem for memory.; The time complexity, while better than brute-force, is still very high.; Can be slower than an optimized backtracking approach in practice due to memory access overhead and the need to compute all `2^N` states.
### Explanation
The core idea is to build up solutions for larger sets of matchsticks from solutions for smaller subsets. A bitmask is a natural way to represent subsets in this context. `dp[mask] = true` will mean that the matchsticks corresponding to set bits in `mask` can be grouped into some number of sides, each with a sum equal to the target side length.

The transition works as follows: for a state `mask` to be valid, it must be possible to form it by taking a previously valid state `prev_mask` and adding a set of sticks `submask` that form exactly one new side. This means `mask = prev_mask | submask`, `dp[prev_mask]` is true, and the sum of sticks in `submask` is equal to the target side length. Iterating through all submasks for each mask allows us to compute the DP table.

```java
class Solution {
    public boolean makesquare(int[] matchsticks) {
        int n = matchsticks.length;
        if (n < 4) return false;
        long perimeter = 0;
        for (int stick : matchsticks) perimeter += stick;
        if (perimeter % 4 != 0) return false;
        long side = perimeter / 4;

        long[] sums = new long[1 << n];
        for (int i = 1; i < (1 << n); i++) {
            int lsbIndex = Integer.numberOfTrailingZeros(i);
            int prevMask = i ^ (1 << lsbIndex);
            sums[i] = sums[prevMask] + matchsticks[lsbIndex];
        }

        boolean[] dp = new boolean[1 << n];
        dp[0] = true;

        for (int mask = 1; mask < (1 << n); mask++) {
            if (sums[mask] % side != 0) continue;
            // Iterate through all submasks of the current mask
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                if (sums[submask] == side) {
                    if (dp[mask ^ submask]) {
                        dp[mask] = true;
                        break;
                    }
                }
            }
        }
        return dp[(1 << n) - 1];
    }
}
```
### Algorithm
- First, perform the same initial checks for perimeter and side length as in the other approaches.
- The problem can be viewed as partitioning the set of matchsticks into 4 disjoint subsets, each summing to the target side length.
- We can use dynamic programming with a bitmask to solve this. A bitmask `mask` can represent a subset of matchsticks. `dp[mask]` will store a boolean value indicating whether the subset of matchsticks represented by `mask` can be perfectly partitioned into sides of length `targetSide`.
- Precompute an array `sums` where `sums[mask]` stores the sum of lengths of matchsticks in the subset represented by `mask`. This can be done in O(N * 2^N) or O(2^N).
- Initialize a boolean DP array `dp` of size `2^N`. Set `dp[0] = true`, as an empty set is a valid partition.
- Iterate through each `mask` from 1 to `(1 << N) - 1`.
- For a given `mask`, `dp[mask]` can be true only if `sums[mask]` is a multiple of `targetSide`.
- To compute `dp[mask]`, we check if it can be formed by adding a valid side to a smaller valid partition. We iterate through all submasks `submask` of `mask`.
- If we find a `submask` such that `sums[submask]` equals `targetSide` and `dp[mask ^ submask]` is true, it means we can form the partition for `mask`. We set `dp[mask] = true` and break the inner loop.
- The final answer is `dp[(1 << N) - 1]`, which tells us if all matchsticks can be partitioned as required.

## Optimized Backtracking with Pruning
This approach is a highly optimized version of the backtracking (DFS) solution. By incorporating several clever pruning techniques, it dramatically reduces the search space. The main idea is to sort the matchsticks in descending order and to avoid exploring symmetric states during the recursion. This makes the solution very fast in practice, often outperforming other approaches for the given constraints.
**Time:** O(4^N). Although the worst-case complexity remains the same as the brute-force approach, the pruning techniques make the effective runtime much, much lower, allowing it to pass for N=15. · **Space:** O(N) for the recursion stack depth.
**Pros:** Very efficient in practice for typical competitive programming constraints.; Low space complexity.; Relatively simple to implement compared to the bitmask DP approach.
**Cons:** The worst-case time complexity is still exponential and hard to analyze precisely.; Performance can be sensitive to the specific input values.
### Explanation
While the brute-force DFS is too slow, we can make it efficient with optimizations. The most impactful optimization is to process the matchsticks from largest to smallest. This forces early decisions on the largest sticks, which have the most constraints on where they can be placed. If a large stick leads to an invalid configuration, we prune that entire branch of the search early.

The second major optimization is to handle symmetry. When we try to place a stick, if multiple sides have the same current length, trying the stick on each of them is redundant. We only need to try it on one of them. The check `if (i > 0 && sides[i] == sides[i-1])` effectively implements this by ensuring that for a given stick, we only try to place it on sides with unique lengths.

```java
import java.util.Arrays;

class Solution {
    public boolean makesquare(int[] matchsticks) {
        if (matchsticks == null || matchsticks.length < 4) {
            return false;
        }
        long perimeter = 0;
        for (int stick : matchsticks) {
            perimeter += stick;
        }
        if (perimeter % 4 != 0) {
            return false;
        }
        long side = perimeter / 4;

        // Sort in descending order for efficient pruning
        Arrays.sort(matchsticks);
        reverse(matchsticks);

        return backtrack(matchsticks, 0, new long[4], side);
    }

    private void reverse(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    private boolean backtrack(int[] matchsticks, int index, long[] sides, long targetSide) {
        if (index == matchsticks.length) {
            return true;
        }

        int currentMatchstick = matchsticks[index];
        for (int i = 0; i < 4; i++) {
            // Pruning to avoid redundant computations on symmetric states
            if (i > 0 && sides[i] == sides[i - 1]) {
                continue;
            }
            
            if (sides[i] + currentMatchstick <= targetSide) {
                sides[i] += currentMatchstick;
                if (backtrack(matchsticks, index + 1, sides, targetSide)) {
                    return true;
                }
                sides[i] -= currentMatchstick; // Backtrack
            }
        }
        return false;
    }
}
```
### Algorithm
- Start with the same initial checks for perimeter and side length.
- **Sort the matchsticks in descending order.** This is a crucial optimization. By trying to place the largest matchsticks first, we can quickly determine if a path is invalid, as they are more likely to make a side exceed the target length. This prunes the search tree significantly.
- Use the same recursive structure `backtrack(index, sides)` as the brute-force approach.
- **Base Case:** If `index` reaches `matchsticks.length`, all sticks have been placed successfully, so return `true`.
- **Recursive Step:** For `matchsticks[index]`, iterate through the four sides `i` from 0 to 3.
- **Pruning 1:** If adding the current matchstick would exceed the `targetSide`, skip this side.
- **Pruning 2:** This is the key optimization to avoid redundant computations on symmetric states. If we are considering placing the current stick on side `i`, and side `i` has the same length as side `i-1` (`sides[i] == sides[i-1]`), we can skip side `i`. This is because if placing the stick on side `i-1` didn't lead to a solution, placing it on side `i` won't either, as the resulting state of the sides would be a permutation of the previous one, leading to the same subproblem.
- If a placement is valid, add the stick to the side, recurse with `index + 1`. If the recursion returns `true`, propagate it. Otherwise, backtrack.

# Solutions
### Java

```java
class Solution {
public
  boolean makesquare(int[] matchsticks) {
    int s = 0, mx = 0;
    for (int v : matchsticks) {
      s += v;
      mx = Math.max(mx, v);
    }
    int x = s / 4, mod = s % 4;
    if (mod != 0 || x < mx) {
      return false;
    }
    Arrays.sort(matchsticks);
    int[] edges = new int[4];
    return dfs(matchsticks.length - 1, x, matchsticks, edges);
  }
private
  boolean dfs(int u, int x, int[] matchsticks, int[] edges) {
    if (u < 0) {
      return true;
    }
    for (int i = 0; i < 4; ++i) {
      if (i > 0 && edges[i - 1] == edges[i]) {
        continue;
      }
      edges[i] += matchsticks[u];
      if (edges[i] <= x && dfs(u - 1, x, matchsticks, edges)) {
        return true;
      }
      edges[i] -= matchsticks[u];
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool makesquare(vector<int> &matchsticks) {
    int s = 0, mx = 0;
    for (int &v : matchsticks) {
      s += v;
      mx = max(mx, v);
    }
    int x = s / 4, mod = s % 4;
    if (mod != 0 || x < mx)
      return false;
    sort(matchsticks.begin(), matchsticks.end(), greater<int>());
    vector<int> edges(4);
    return dfs(0, x, matchsticks, edges);
  }
  bool dfs(int u, int x, vector<int> &matchsticks, vector<int> &edges) {
    if (u == matchsticks.size())
      return true;
    for (int i = 0; i < 4; ++i) {
      if (i > 0 && edges[i - 1] == edges[i])
        continue;
      edges[i] += matchsticks[u];
      if (edges[i] <= x && dfs(u + 1, x, matchsticks, edges))
        return true;
      edges[i] -= matchsticks[u];
    }
    return false;
  }
};

```

### Python

```python
class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool: def dfs(u): if u == len(matchsticks): return True for i in range(4): if i > 0 and edges[i - 1] == edges[i]: continue edges[i] += matchsticks[u] if edges[i] <= x and dfs(u + 1): return True edges[i] -= matchsticks[u] return False x, mod = divmod(sum(matchsticks), 4) if mod or x < max(matchsticks): return False edges = [0] * 4 matchsticks . sort(reverse=True) return dfs(0)

```