1.LeetCode473题目链接
https://leetcode-cn.com/problems/matchsticks-to-square/submissions/
2.解题思路
首先我们将不能组成正方形的结果去除，边长不能整除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;
}
}
//群里同学说现排序效率更高，试了下，提高了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
