1先鱼、題目
火柴拼正方形 - 力扣（LeetCode） https://leetcode-cn.com/problems/matchsticks-to-square/
2、題解
首先我們可以對(duì)所有火柴進(jìn)行求和掸读，如果sum不能整除4儿惫，說(shuō)明無(wú)論如何都無(wú)法拼湊出正方形伸但。然后我們嘗試將火柴分配到四個(gè)邊長(zhǎng)更胖，如果最后四邊都相等，則說(shuō)明可以拼湊避归。
3管呵、代碼
class Solution {
public boolean makesquare(int[] nums) {
if (nums.length == 0) {
return false;
}
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 4 != 0) {
return false;
}
int target = sum / 4;
return ResultForDPS(nums, 0, target, target, target, target);
}
private boolean ResultForDPS(int[] nums, int index, int one, int two, int three, int four) {
if(index==nums.length){
return one==two&&two==three&&three==four;
}
if(one<0||two<0||three<0||four<0){
return false;
}
return ResultForDPS(nums,index+1,one-nums[index],two,three,four)||
ResultForDPS(nums,index+1,one,two-nums[index],three,four)||
ResultForDPS(nums,index+1,one,two,three-nums[index],four)||
ResultForDPS(nums,index+1,one,two,three,four-nums[index]);
}
}
4账锹、執(zhí)行結(jié)果
image.png
