Matchsticks to Square
给一个数组, 问能不能用其中的数, 组成一个正方形. 能组成正方形,就是四等分. 所以穷举即可.
public class Solution {
public boolean makesquare(int[] nums) {
if(nums == null || nums.length < 4)
return false;
int sum = 0;
for(int n : nums)
sum += n;
if(sum%4 != 0)
return false;
Arrays.sort(nums);
reverse(nums);
return dfs(nums, new int[4], sum/4, 0);
}
public boolean dfs(int[] nums, int[] sum, int target, int index) {
if(nums.length == index){
if(sum[0] == target && sum[1] == target && sum[2] == target && sum[3] == target)
return true;
else
return false;
}
for(int i = 0 ; i < 4; i++) {
if(sum[i]+nums[index] <= target){
sum[i] += nums[index];
if(dfs(nums,sum,target,index+1))
return true;
sum[i] -= nums[index];
}
}
return false;
}
private void reverse(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++; j--;
}
}
}