c++ 3ms using only three times dfs without extra space


  • 0
    L
    class Solution {
    public:
        bool makesquare(vector<int>& nums) {
            if(nums.size()<4)return false;
            int sum =0;
            for(auto n:nums)sum += n;
            if(sum%4)return false;
            sort(nums.begin(),nums.end(),greater<int>());
            return dfs(nums,0,0,sum/4,0);
        }
        
        bool dfs(vector<int>& nums,int pos,int cur,int target,int cnt){
            if(cnt == 3)return true;
            cur += nums[pos++];
            if(cur>target)return false;
            //if match then beign dfs again
            if(cur==target&&dfs(nums,pos,0,target,cnt+1))return true;
            for(int i=pos;i<nums.size();i++){
                swap(nums[i],nums[pos]);
                if(dfs(nums,pos,cur,target,cnt))return true;
                swap(nums[i],nums[pos]);
            }
            return false;
        }
    };
    

Log in to reply
 

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