Matchsticks to Square

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int total = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (total % 4 != 0) return false;
        int side = total / 4;
        sort(matchsticks.rbegin(), matchsticks.rend());
        if (matchsticks[0] > side) return false;
        vector<int> sides(4, 0);
        function<bool(int)> dfs = [&](int i) {
            if (i == (int)matchsticks.size()) return sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3];
            for (int k = 0; k < 4; ++k) {
                if (sides[k] + matchsticks[i] > side) continue;
                // Skip identical-side states.
                if (k > 0 && sides[k] == sides[k - 1]) continue;
                sides[k] += matchsticks[i];
                if (dfs(i + 1)) return true;
                sides[k] -= matchsticks[i];
            }
            return false;
        };
        return dfs(0);
    }
};

import "sort"

func makesquare(matchsticks []int) bool {
    total := 0
    for _, v := range matchsticks {
        total += v
    }
    if total%4 != 0 {
        return false
    }
    side := total / 4
    sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))
    if matchsticks[0] > side {
        return false
    }
    sides := make([]int, 4)
    var dfs func(i int) bool
    dfs = func(i int) bool {
        if i == len(matchsticks) {
            return sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3]
        }
        for k := 0; k < 4; k++ {
            if sides[k]+matchsticks[i] > side {
                continue
            }
            if k > 0 && sides[k] == sides[k-1] {
                continue
            }
            sides[k] += matchsticks[i]
            if dfs(i + 1) {
                return true
            }
            sides[k] -= matchsticks[i]
        }
        return false
    }
    return dfs(0)
}

from typing import List

class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        total = sum(matchsticks)
        if total % 4 != 0:
            return False
        side = total // 4
        matchsticks.sort(reverse=True)
        if matchsticks[0] > side:
            return False
        sides = [0] * 4

        def dfs(i: int) -> bool:
            if i == len(matchsticks):
                return sides[0] == sides[1] == sides[2] == sides[3]
            for k in range(4):
                if sides[k] + matchsticks[i] > side:
                    continue
                # Skip identical-side states.
                if k > 0 and sides[k] == sides[k - 1]:
                    continue
                sides[k] += matchsticks[i]
                if dfs(i + 1):
                    return True
                sides[k] -= matchsticks[i]
            return False

        return dfs(0)

function makesquare(matchsticks) {
    const total = matchsticks.reduce((a, b) => a + b, 0);
    if (total % 4 !== 0) return false;
    const side = total / 4;
    matchsticks.sort((a, b) => b - a);
    if (matchsticks[0] > side) return false;
    const sides = [0, 0, 0, 0];
    const dfs = (i) => {
        if (i === matchsticks.length) {
            return sides[0] === sides[1] && sides[1] === sides[2] && sides[2] === sides[3];
        }
        for (let k = 0; k < 4; k++) {
            if (sides[k] + matchsticks[i] > side) continue;
            if (k > 0 && sides[k] === sides[k - 1]) continue;
            sides[k] += matchsticks[i];
            if (dfs(i + 1)) return true;
            sides[k] -= matchsticks[i];
        }
        return false;
    };
    return dfs(0);
}

class Solution {
    private int[] matchsticks;
    private int side;
    private int[] sides;

    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int v : matchsticks) total += v;
        if (total % 4 != 0) return false;
        side = total / 4;
        // Sort descending.
        Arrays.sort(matchsticks);
        for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
            int t = matchsticks[i]; matchsticks[i] = matchsticks[j]; matchsticks[j] = t;
        }
        if (matchsticks[0] > side) return false;
        this.matchsticks = matchsticks;
        sides = new int[4];
        return dfs(0);
    }

    private boolean dfs(int i) {
        if (i == matchsticks.length) {
            return sides[0] == sides[1] && sides[1] == sides[2] && sides[2] == sides[3];
        }
        for (int k = 0; k < 4; k++) {
            if (sides[k] + matchsticks[i] > side) continue;
            if (k > 0 && sides[k] == sides[k - 1]) continue;
            sides[k] += matchsticks[i];
            if (dfs(i + 1)) return true;
            sides[k] -= matchsticks[i];
        }
        return false;
    }
}

function makesquare(matchsticks: number[]): boolean {
    const total = matchsticks.reduce((a, b) => a + b, 0);
    if (total % 4 !== 0) return false;
    const side = total / 4;
    matchsticks.sort((a, b) => b - a);
    if (matchsticks[0] > side) return false;
    const sides: number[] = [0, 0, 0, 0];
    const dfs = (i: number): boolean => {
        if (i === matchsticks.length) {
            return sides[0] === sides[1] && sides[1] === sides[2] && sides[2] === sides[3];
        }
        for (let k = 0; k < 4; k++) {
            if (sides[k] + matchsticks[i] > side) continue;
            if (k > 0 && sides[k] === sides[k - 1]) continue;
            sides[k] += matchsticks[i];
            if (dfs(i + 1)) return true;
            sides[k] -= matchsticks[i];
        }
        return false;
    };
    return dfs(0);
}