1命辖、前言
題目描述
2、思路
3、代碼
class Solution {
public boolean makesquare(int[] matchsticks) {
int total = 0;
for (int num : matchsticks) {
total += num;
}
if(total == 0 || total % 4 != 0){
return false;
}
Arrays.sort(matchsticks);
return backTrack(matchsticks, 0, total / 4, new int[4]);
}
private boolean backTrack(int[] nums, int index, int target, int[] size){
if(index == nums.length){
if(size[0] == size[1] && size[1] == size[2] && size[2] == size[3]){
return true;
}
return false;
}
for(int i = 0; i < size.length; i++){
if(size[i] + nums[index] > target){
continue;
}
size[i] += nums[index];
if(backTrack(nums, index + 1, target, size)){
return true;
}
size[i] -= nums[index];
}
return false;
}
}
