C++ DFS 3ms


  • 0
    Y
    class Solution {
        vector<bool> choosen;
    public:
        bool makesquare(vector<int>& nums) {
            int peri = accumulate(begin(nums), end(nums), 0);
            if( nums.size()<=3 || peri%4 != 0) return false;
            int target = peri/4;
            sort(nums.begin(), nums.end(), std::greater<int>());
            if(nums[0]>target) return false;
            
            choosen.resize(nums.size(), false);
            
            for(int i=0; i<3; ++i) {
                if (false == DFS(nums, 0, target)) {
                    return false;
                }
            }
            return true;
        }
        
        bool DFS(vector<int> &nums, int start, int target) {
            int ans = false;
            
            for(int i=start; i<nums.size(); ++i) {
                if(choosen[i]==true) continue;
                
                if(nums[i]==target) {
                    choosen[i] = true;
                    ans = true;
                    break;
                }
                if(nums[i] < target) {
                    if(DFS(nums, i+1, target-nums[i])) {
                        choosen[i] = true;
                        ans = true;
                        break;
                    }
                }
            }
            
            return ans;
        }
    };
    

Log in to reply
 

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