Clean 6ms C++ DFS solution


  • 0
    J
    class Solution {
    public:
        bool DFS(vector<int>& nums, vector<bool> &used, int start, int leftlength)
        {
            if(leftlength == 0) return true;
            if(leftlength < 0) return false;
            for(int i = start; i < nums.size(); i++)
            {
                if(used[i]) continue;
                used[i] = true;
                if(DFS(nums, used, i+1, leftlength-nums[i])) return true;
                used[i] = false;
            }
            return false;
        }
        
        bool makesquare(vector<int>& nums) {
            if(nums.size() < 4) return false;
            int sum = 0;
            for(int i = 0; i < nums.size(); i++)
                sum = sum + nums[i];
            if(sum%4 > 0) return false;
            int edgelength = sum/4;
            //order the number from big to small to avoid putting small numbers together
            sort(nums.rbegin(), nums.rend());
            vector<bool> used(nums.size(), false);
            for(int i = 0; i < nums.size(); i++)
            {
                if(used[i]) continue;
                if(!DFS(nums, used, i, edgelength)) return false;
            }
            return true;
        }
    };
    

Log in to reply
 

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