Matchsticks to Square

We are given list of match sticks we wanted to know if these matchsticks can form a square

Problem Statement

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 form one square.

You cannot break any matchstick, but you can link them together. Each matchstick must be used exactly once.

Return true if you can form the square, or false otherwise.

Examples

Example 1

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

Output: true

Explanation: You can form a square with side length 2. One side of the square is made up of two matchsticks of length 1.

Example 2

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

Output: false

Explanation: There is no way to arrange all the matchsticks into a valid square.

Constraints

• 1 ≤ matchsticks.length ≤ 15
• 1 ≤ matchsticks[i] ≤ 10⁸ (this value appeared as "108" in the original text — it most likely means 10⁸, but you may want to double-check the original source)

Solution

Since a square has 4 equal sides, we first need to figure out what the length of each side should be. Then, we try to distribute all the matchsticks across 4 sides so that each side ends up with exactly that length.

Steps

• First, we calculate the total length of all matchsticks combined.
• If this total is not evenly divisible by 4, it's impossible to form a square, so we return false right away.
• Otherwise, we calculate the target side length: total / 4.
• We sort the matchsticks in descending order (largest first). This is a small optimization — placing the biggest matchsticks first tends to narrow down our options faster and fail early if something won't work, instead of wasting time trying many small combinations first.
• We keep track of 4 running totals in an array called sides, one for each side of the square.
• We use a helper function, backtrack(index), to try placing each matchstick, one at a time:
  • If we've placed every matchstick (index equals the total count), we check if all 4 sides ended up exactly equal to our target side length. If so, we've successfully formed a square.
  • Otherwise, we try adding the current matchstick to each of the 4 sides, one at a time:
    • We only try adding it to a side if doing so doesn't exceed the target side length.
    • If we add it, we move on and try to place the next matchstick, using recursion.
    • If that doesn't lead to a full solution, we remove the matchstick from that side (backtrack), and try adding it to a different side instead.
  • If none of the 4 sides work for this matchstick, we return false, so an earlier step can try a different arrangement.

Code

var makesquare = function(matchsticks) {
    let total = matchsticks.reduce((a, b) => a + b);
    matchsticks.sort((a, b) => b - a);
    if (total % 4 !== 0) return false;

    const side = total / 4;

    const sides = [0, 0, 0, 0];

    function backtrack(index) {
        if (index == matchsticks.length) {
            return sides.every(s => s === side);
        }

        for (let i = 0; i < 4; i++) {
            if (matchsticks[index] + sides[i] <= side) {

                sides[i] += matchsticks[index];

                if (backtrack(index + 1)) {
                    return true;
                }

                sides[i] -= matchsticks[index];
            }
        }

        return false;
    }

    return backtrack(0);
};