LeetCode_回溯_中等_473.火柴拼正方形

太过爱你忘了你带给我的痛 2023-10-06 23:38 28阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

你将得到一个整数数组 matchsticks ，其中 matchsticks\[i\] 是第 i 个火柴棒的长度。你要用所有的火柴棍拼成一个正方形。**你不能折断任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须使用一次。**

如果你能使这个正方形，则返回 true ，否则返回 false。

**示例 1：**  
![在这里插入图片描述][c17c5952c1ea434eac2f4af026c276a1.png]  
输入: matchsticks = \[1,1,2,2,2\]  
输出: true  
解释: 能拼成一个边长为 2 的正方形，每边两根火柴。

**示例 2：**  
输入: matchsticks = \[3,3,3,3,4\]  
输出: false  
解释: 不能用所有火柴拼成一个正方形。

**提示：**  
1 <= matchsticks.length <= 15  
1 <= matchsticks\[i\] <= 108

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/matchsticks-to-square

## 2.思路 ##

（1）回溯算法  
此题可以看作[698.划分为k个相等的子集][698._k]这题的变形，如果所有的火柴棍可以拼成一个正方形，那么我们必定可以将数组 matchsticks 划分为 4 个和相等的子集，反之也必然。所以本题只需判断能否将数组 matchsticks 划分为 4 个和相等的子集即可，如果可以返回 true，否则返回 false。

相关题目：  
[LeetCode\_回溯\_中等\_698.划分为k个相等的子集][698._k]

## 3.代码实现（Java） ##

//思路1————回溯
    class Solution {
        
        public boolean makesquare(int[] matchsticks) {
        
            int sum = 0;
            for (int matchstick : matchsticks) {
        
                sum += matchstick;
            }
            //所有火柴长度之和必须是 4 的倍数
            if (sum % 4 != 0) {
        
                return false;
            }
            int k = 4;
            //定义 k 个桶(集合)，每个桶记录装入当前桶的元素之和
            int[] buckets = new int[k];
            //理论上每个桶中的元素之和为 sum / k
            int target = sum / k;
            /*
                (1) 对数组 matchsticks 进行降序排序，sort()默认是升序排序，但是 matchsticks 是 int[]，而非 
                    Integer[]，所以无法直接重写 Arrays.sort() 的比较器 Comparator 的 compare() 方法
                (2) 提前对 matchsticks 数组排序，把大的数字排在前面，那么大的数字会先被分配到 bucket 中，
                    对于之后的数字，bucket[i] + matchsticks[index] 会更大，更容易触发剪枝的 if 条件。
            */
            Arrays.sort(matchsticks);
            for (int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
        
                // 交换 nums[i] 和 nums[j]
                int temp = matchsticks[i];
                matchsticks[i] = matchsticks[j];
                matchsticks[j] = temp;
            }
            return backtrack(matchsticks, 0, buckets, target);
        }
        
        private boolean backtrack(int[] matchsticks, int index, int[] buckets, int target) {
        
            if (index == matchsticks.length) {
        
                return true;
            }
            for (int i = 0; i < buckets.length; i++) {
        
            	if (i > 0 && buckets[i] == buckets[i - 1]) {
        
                    continue;
                }
                //当前桶已经装满
                if (buckets[i] + matchsticks[index] > target) {
        
                    continue;
                }
                buckets[i] += matchsticks[index];
                if (backtrack(matchsticks, index + 1, buckets, target)) {
        
                    return true;
                }
                buckets[i] -= matchsticks[index];
            }
            // matchsticks[index] 不能装入任何一个桶
            return false;
        }
    }

[c17c5952c1ea434eac2f4af026c276a1.png]: https://img-blog.csdnimg.cn/c17c5952c1ea434eac2f4af026c276a1.png
[698._k]: https://blog.csdn.net/weixin_43004044/article/details/123589576