473

class Solution {
public:
    bool makesquare(vector<int>& sticks) {
        int sum = 0;
        for(auto num: sticks)
            sum += num;
        if(sum%4) return false;
        sort(sticks.rbegin(), sticks.rend());
        vector<int> sums(4, 0);
        return dfs(sum/4, sums, 0, sticks);
    }

    bool dfs(int target, vector<int> &sums, int idx, vector<int> &sticks){
        if(idx == sticks.size()){
            if(sums[0] == target && sums[1] == target && sums[2] == target)
                return true;
            else
                return false;
        }
        for(int i=0; i<4; i++){
            if(sticks[idx]+sums[i] > target) continue;
            sums[i] += sticks[idx];
            if(dfs(target, sums, idx+1, sticks)) return true;
            sums[i] -= sticks[idx];
        }
        return false;
    }

};