My 29ms cpp dfs/backtracking solution


  • 0
    L
    class Solution {
    public:
        bool makesquare(vector<int>& nums) {
            int n = nums.size();
            if (n < 4)  return false;
            int sum = 0;
            for (int num : nums) {
                sum += num;
            }
            if (sum % 4 != 0)   return false;
            int edge = sum / 4;
            vector<int> aux(2);
            vector<int> left;
            vector<int> right;
            return dfs(nums, aux, left, right, edge * 2, edge, 0);
        }
    private :
        bool dfs(vector<int>& nums, vector<int>& aux, vector<int>& left, vector<int>& right, int target, int edge, int index) {
            if (index == nums.size()) {
                if (target == 2 * edge && aux[0] == target) {
                    vector<int> a1(2), a2(2), l1, l2, r1, r2;
                    return dfs(left, a1, l1, r1, edge, edge, 0) && dfs(right, a2, l2, r2, edge, edge, 0);
                } 
                if (target == edge && aux[0] == target) {
                    return true;
                }
                return false;
            }
            
            if (aux[0] + nums[index] <= target) {
                aux[0] += nums[index];
                left.push_back(nums[index]);
                if(dfs(nums, aux, left, right, target, edge, index + 1)) return true;
                aux[0] -= nums[index];
                left.pop_back();
            }
            
            if (aux[1] + nums[index] <= target) {
                aux[1] += nums[index];
                right.push_back(nums[index]);
                if (dfs(nums, aux, left, right, target, edge, index + 1)) return true;
                aux[1] -= nums[index];
                right.pop_back();
            }
            return false;
        }
    };
    

Log in to reply
 

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