思路回溯 剪枝基本判断所有火柴总长度必须能被 4 整除最长的那根火柴不能超过正方形边长 target total / 4。核心搜索把每根火柴依次尝试放进 4 条边中用 sides[4] 记录每条边当前已放置的长度。放满 4 条边即成功。关键剪枝否则会超时从大到小排序长火柴先放分支更少相同边跳过如果 sides[i] sides[i-1]说明这两条边当前状态一样尝试一条即可空边失败剪枝如果某根火柴放进一条空边后搜索失败直接返回 false。因为放在哪条空边都等价满边失败剪枝如果某根火柴放进后该边正好填满但后续搜索失败直接返回 false。因为填满这条边是必然的无需换其他边尝试。Java 实现importjava.util.Arrays;classSolution{publicbooleanmakesquare(int[]matchsticks){inttotal0;for(intm:matchsticks)totalm;if(total%4!0)returnfalse;inttargettotal/4;intnmatchsticks.length;// 从大到小排序Arrays.sort(matchsticks);for(inti0,jn-1;ij;i,j--){inttmpmatchsticks[i];matchsticks[i]matchsticks[j];matchsticks[j]tmp;}if(matchsticks[0]target)returnfalse;int[]sidesnewint[4];returnbacktrack(matchsticks,0,sides,target);}privatebooleanbacktrack(int[]nums,intidx,int[]sides,inttarget){if(idxnums.length){// 走到这里所有火柴都已放置且每根都满足 target// 只要总和 4 * target则四条边必然都等于 targetreturntrue;}for(inti0;i4;i){// 剪枝 1放不下if(sides[i]nums[idx]target)continue;// 剪枝 2跳过状态相同的边if(i0sides[i]sides[i-1])continue;sides[i]nums[idx];if(backtrack(nums,idx1,sides,target))returntrue;sides[i]-nums[idx];// 剪枝 3空边放入失败直接返回if(sides[i]0)returnfalse;// 剪枝 4正好填满边但失败直接返回if(sides[i]nums[idx]target)returnfalse;}returnfalse;}}代码说明· idx nums.length 时直接返回 true因为每根火柴放入时都保证 sides[i] nums[idx] target所有火柴放完后总长度恰好是 4 * target所以四条边必然都等于 target。· 剪枝 3 的判断sides[i] 已在上一行减回去所以此时 sides[i] 0 表示放入之前该边为空。空边都放不下其他空边也一样直接失败。· 剪枝 4 的判断sides[i] nums[idx] target 表示放入之后该边正好填满。如果这种情况失败说明这根火柴必须放在这条边上而不行换边也一样直接失败。复杂度· 时间复杂度最坏 O(4^n)但剪枝后实际远小于此。· 空间复杂度O(n)递归栈深度 排序开销 O(log n)。易错点忘记倒序排序从小到大排会大幅增加搜索分支容易 TLE剪枝 3 和剪枝 4 的判断时机必须在 sides[i] - nums[idx] 之后判断否则 sides[i] 还是放入后的值判断会出错matchsticks[0] target 的检查倒序排序后 matchsticks[0] 是最长火柴必须提前拦截idx nums.length 直接返回 true 即可不需要再逐个比较四条边因为中途的 target 约束已经保证总和分配正确。
