# My 29ms cpp dfs/backtracking solution

• ``````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;
}
};
``````

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