my C++ 9ms solution


  • 1
    G
    #include <vector>
    using namespace std;
    
    class Solution {
    public:
        bool makesquare(vector<int>& nums) {
            n = nums.size() + 1;
    
            long long sum = 0, a;
            for (int x : nums)
                sum += x;
            if (sum % 4 != 0)
                return false;
            a = sum / 4;
    
            vector<int> ans;
            choice(0, nums, ans, 0, a);
            int m = ans.size();
            int ai, aj, ak, al;
            for (int i = 0; i < m; ++i) {
                ai = ans[i];
                for (int j = i + 1; j < m; ++j) {
                    aj = ans[j];
                    if (ai & aj)
                        continue;
                    aj |= ai;
                    for (int k = j + 1; k < m; ++k) {
                        ak = ans[k];
                        if (aj & ak)
                            continue;
                        ak |= aj;
                        for (int l = k + 1; l < m; ++l) {
                            al = ans[l];
                            if (ak & al)
                                continue;
                            return true;
                        }
                    }
                }
            }
            return false;
        }
    private:
        int n;
        void choice(int choc, vector<int>& nums, vector<int>& ans, int depth, int rest)
        {
            if (rest == 0) {
                ans.push_back(choc);
                return;
            }
            if (depth == n)
                return;
    
            int w = nums[depth];
            if (rest >= w) {
                choice(choc | (1 << depth), nums, ans, depth + 1, rest - w);
            }
            choice(choc, nums, ans, depth + 1, rest);
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.