1.LeetCode473題目鏈接
https://leetcode-cn.com/problems/matchsticks-to-square/submissions/
2.解題思路
首先我們將不能組成正方形的結(jié)果去除驰徊，邊長不能整除4的笤闯，然后記錄正方形變長，遞歸累加到每個邊等于變長棍厂，若可以得到四條邊則為true颗味。
public boolean makesquare(int[] nums) {
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum == 0 || sum % 4 != 0) {
return false;
}
int target = sum / 4;
for (int num : nums) {
if (num > target) {
return false;
}
}
//群里同學(xué)說現(xiàn)排序效率更高，試了下牺弹，提高了40%的效率浦马。。
Arrays.sort(nums);
search(nums.length - 1, nums, target, new int[4]);
return ans;
}
boolean ans = false;
void search(int cur, int[] nums, int target, int[] temp) {
if (ans){
return;
}
if (cur == -1) {
for (int num : temp) {
if (num != target)
return;
}
ans = true;
return;
}
for (int i = 0; i < temp.length; i++) {
int last = temp[i];
temp[i] += nums[cur];
if (temp[i] <= target) {
search(cur - 1, nums, target, temp);
}
temp[i] = last;
}
}
image
