C++ 6ms code, quite straightforward


  • 0
    S
    bool cmp(int a, int b){
        return a > b;
    }
    class Solution {
    public:
        bool makesquare(vector<int>& nums) {
            int lengthsum =0;
            for(auto c:nums){
                lengthsum += c;
            }
            if(lengthsum <= 0 || lengthsum % 4 != 0){
                return false;
            }
            int sidelength = lengthsum / 4;
            sort(nums.begin(), nums.end(), cmp);
            vector<bool> used(nums.size(), false);
            bool flag = false; int sides = 0;
            for(int i = 0; i < nums.size(); i++){
                if(!used[i]){
                    flag = checkside(nums, i, used, sidelength);
                    if(flag == false){
                        return false;
                    }
                    else{
                        sides++;
                        if(sides == 3){
                            return true;
                        }
                    }
                }
            }
            return true;
        }
        
        bool checkside(vector<int> &nums, int idx, vector<bool> &used, int remainlength){
            used[idx] = true;
            remainlength -= nums[idx];
            if(remainlength == 0){
                return true;
            }
            bool flag;
            for(int i = idx + 1; i < nums.size(); i++){
                if(used[i]){
                    continue;
                }
                if(nums[i] <= remainlength){
                    if(checkside(nums, i, used, remainlength)){
                        return true;
                    }
                }
            }
            used[idx] = false;
            return false;
        }
        
    };

  • 0
    B
    This post is deleted!

  • 0
    B
    This post is deleted!

Log in to reply
 

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