My Solution
This question is talking about split the array into 4 groups, they equal to each other.
-- sum the array and divide by 4, calculate the length of edge.
-- using dfs solution, to divide each number into 4 group, to check true or false.
-- when divide, check whether each group sum larger than edge.
public class Solution {
public boolean makesquare(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 4 != 0 || sum == 0) return false;
int edge = sum / 4;
int[] box = new int[4];
if(helper(nums,box,edge,0)){
for(int b : box){
if(b != edge)return false;
}
return true;
}
return false;
}
public boolean helper(int[] nums, int[] box, int edge, int start) {
if (start == nums.length) return true;
int n = nums[start];
for (int i = 0; i < 4; i++) {
if (box[i] + n <= edge) {
box[i] += n;
if (helper(nums, box, edge, start + 1)) return true;
box[i] -= n;
}
}
return false;
}
}
optimization
Sort the array in descending order can speed up the dfs.
