bool makesquare(int* matchsticks, int matchsticksSize) {
    int totalLen = 0;
    for (int i = 0; i < matchsticksSize; i++) {
        totalLen += matchsticks[i];
    }
    if (totalLen % 4 != 0) {
        return false;
    }
    int len = totalLen / 4, n = matchsticksSize;
    int *dp = (int *)malloc(sizeof(int) * (1 << n));
    memset(dp, -1, sizeof(int) * (1 << n));
    dp[0] = 0;
    for (int s = 1; s < (1 << n); s++) {
        for (int k = 0; k < n; k++) {
            if ((s & (1 << k)) == 0) {
                continue;
            }
            int s1 = s & ~(1 << k);
            if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
                dp[s] = (dp[s1] + matchsticks[k]) % len;
                break;
            }
        }
    }
    bool res = dp[(1 << n) - 1] == 0;
    free(dp);
    return res;
}