473. 火柴拼正方形
解题思路第一,目标就是把数组里面的数,分到四个堆里面。
第二,就是把每个数分到不同的堆里面进行尝试,直到最后都分配完成了,此时判断能否满足要求,
第三,在回溯尝试的过程中,对于已经超出总数的25%的就直接停止,不用继续回溯了。
错误的解题代码下面的代码将p函数执行4次,即每次从数组里面选择满足和为 sum/4 的一组,若4次都是true,则返回true。
这个解法的错误在于,第一次选虽然满足了第一租的要求,但是错误的把要分配给2 3 4租的数字给用了,导致2 3 4组没办法成功了 例如这组用例
[13,11,1,8,6,7,8,8,6,7,8,9,8]
class Solution {
public boolean makesquare(int[] matchsticks) {
int sum = 0;
for (int i :matchsticks ){
sum += i;
}
if (sum%4!=0){
return false;
}
Arrays.sort(matchsticks);
boolean[] b = new boolean[matchsticks.length];
int l = sum/4;
return p(matchsticks,b,l) && p(matchsticks,b,l) && p(matchsticks,b,l) &&p(matchsticks,b,l);
}
private boolean p(int[] matchsticks, boolean[] b, int l) {
if (l==0){
return true;
} else if (l<0){
return false;
} else{
for (int i=matchsticks.length-1;i>=0;i--){
if (!b[i]){
b[i] = true;
if (p(matchsticks,b,l-matchsticks[i])){
return true;
}
b[i] = false;
}
}
return false;
}
}
}
正确的解题代码
第一,先求和,并判断能够平分4份,
第二,通过回溯的方式,得到答案。
第三,进行大优化,先给数组排序,处理的顺序按照从大到小。保证全部用例不超时
第四,进行小优化,把回溯的第一个数固定到第一组。
public class Solution473 {
int[] matchsticks;
int end;
public static void main(String[] args) {
boolean a = new Solution473().makesquare(new int[]{13, 11, 1, 8, 6, 7, 8, 8, 6, 7, 8, 9, 8});
System.out.println(a);
}
public boolean makesquare(int[] matchsticks) {
Arrays.sort(matchsticks);
this.matchsticks = matchsticks;
int sum = 0;
for (int i : matchsticks) {
sum += i;
}
this.end = sum / 4;
if (sum % 4 != 0) {
return false;
}
int[] s = new int[4];
s[0] = matchsticks[matchsticks.length-1];
return p1(matchsticks.length-2,s);
}
private boolean p1(int i ,int[] s){
if (this.end == s[0] && this.end==s[1] && this.end==s[2]&& this.end==s[3]){
return true;
}else {
if (i<0){
return false;
}
if (s[0]>end || s[1]>end || s[2]>end || s[3]>end ){
return false;
}
boolean res = false;
for (int j =0;j<4;j++){
s[j] += this.matchsticks[i];
res = res ||p1(i-1,s);
s[j] -= this.matchsticks[i];
}
return res;
}
}
}
解题结果
一轮优化后,通过了全部用例。
二轮优化后,提升了性能。



