MATCHSTICKS_TO_SQUARE

class Solution {
public:
    bool myfunc(vector<int> &M, int sum, vector<int> &vis, vector<int> &S, int idx) {

        if(idx == M.size()) {
            if(S[0] == sum and S[1] == sum and S[2] == sum and S[3] == sum) {
                return true;
            }
        }


        for(int i = 0; i < 4; ++i) {
            if(vis[idx] or S[i] + M[idx] > sum) {
                continue;
            }
            vis[idx] = true;
            //include
            S[i] += M[idx];
            if(myfunc(M, sum, vis, S, idx + 1)) {
                return true;
            }
            //exclude
            S[i] -= M[idx];
            vis[idx] = false;

        }
        return false;
    }


    bool makesquare(vector<int>& M) {
        int sum = 0;

        sum = accumulate(M.begin(), M.end(), sum);
        sort(M.rbegin(), M.rend());

        if(M.size() < 4 or sum%4) {
            return false;
        }
        sum/=4;
        vector<int> vis(M.size(),0); //visited
        vector<int> S(4,0); //sides


        return myfunc(M, sum, vis, S, 0);
    }
};