“集合划分问题”如何解决？这里教你个妙招，轻松掌握这类问题~

待我称王封你为后i 2024-03-30 03:22 69阅读 0赞

**目录**

“集合划分”这类问题的解题思路

一、划分为k个相等的子集

二、火柴拼正方形

--------------------

## “集合划分”这类问题的解题思路 ##

这类题一般都会描述成这个样子：“给你一个数组，是否能将他划分成n个数值相等的子集？”，再或者有些可能题目描述稍微优点隐晦（下面会给出栗子），这类问题实际上是有通法的，通过 “桶 + 回溯 + 剪枝” 的思路便可以迎刃而解；

> 什么是 “桶 + 回溯 + 剪枝” 呢？

根据题目描述，是让你把数组划分成n个数值相等的子集，即每一个子集的和都是一样的，那么我们就可以求出每一个子集的和是多少（就是把数组每一个值加起来，然后除以要划分的子集个数），那桶是干什么的呢？我们可以用n个桶来装这些子集，每个桶的容量便是子集的和；以下将用一个栗子让你更加清楚~

假设数组nums为\[1, 1, 2, 2, 2\] ，是否能划分成4个相等子集？

> 解决过程如下：

先给数组求和，即sum = 8，要将他划分成4个相等的子集，也就是说每个子集的大小因该为sum / 4 = 2，那么便可以创建4个桶，每一个桶的大小为2；

nums\[0\] = 1，用第一个桶来装，能装下，并且还剩一个位置；nums\[1\] = 1，继续用第一个桶来装，能正好能把第一个桶装满；nums\[2\] = 2，用第一个桶来装，发现装不下了，就往第二个桶里装，正好能装满；nums\[3\] = 2，用第一个桶来装，装不下，在试试用第二个桶来装，装不下，就往第三个桶里装，发现正好能装满；nums\[4\] = 2，用第一个桶，装不下、用第二个桶，装不下、用第三个桶，装不下、用第四个桶正好能装下；这时候可以发现，**四个桶都装满了，那么回原问题上，就相当于可以划分为四个相等的子集**；

以上便是一个dfs的全过程，若放错桶，不能将每个桶装满，并且还有剩余数字没有放入桶中，这时便可以回溯回去，再试试其他可能；

> 如何剪枝呢？

剪枝一：降序排序

不排序也能做对，但是时间上开销就相对较大了，为什么降序排序就可以优化时间呢？我们从num中最大的数开始找，若最大的数都要比子集还要大，或者装下它后，没有装满桶，但是装不下nums中的最小值了，那么这个题的答案一定是false，因为这样一个数的存在，放在哪一个桶里都不合适，通过降序排序，就可以提早发现这个问题，并直接返回false解决；

剪枝二：回溯时若桶的大小等于0，直接返回false

这就表示，如果前面做出选择之后，递归完没有找到任何一个合适的值装满桶，那么回溯撤掉这个值以后，一定为零；比如桶的大小为4，桶中加入了3，但是递归完，发现不存在长度为1的，那么回溯撤掉这个值后桶的大小就是0了；

> 以上便是这类问题的通解，接下来的两道题，便是“集合划分”的经典问题，思路不能说相似，简直是完全一样；

--------------------

## 一、划分为k个相等的子集 ##

> 题目描述

给定一个整数数组 `nums` 和一个正整数 `k`，找出是否有可能把这个数组分成 `k` 个非空子集，其总和都相等。

> 示例：

输入： nums = \[4, 3, 2, 3, 5, 2, 1\], k = 4  
输出： True  
说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。

题目来源：[698. 划分为k个相等的子集 - 力扣（LeetCode）][698. _k_ - _LeetCode]

> 代码如下：

class Solution {
    
        public boolean canPartitionKSubsets(int[] nums, int k) {
            if(nums.length < k) {//比均分的数目还小就肯定不能均分
                return false;
            }
            int sum = 0;
            for(int i = 0; i < nums.length; i++) {
                sum += nums[i];
            }
            if(sum % k != 0) {//想要均分成k个区间，那么每个区间的值一定相等，因此sum一定能被k整除
                return false;
            }
            int len = sum / k;//每个区间要满足的大小
            //桶
            int[] bucket = new int[k];
            //剪枝：倒序效率更高
            Arrays.sort(nums);
            for(int i = 0, j = nums.length - 1; i < j; i++, j--) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }
            return dfs(nums, bucket, len, k, 0);
        }
    
        private boolean dfs(int[] nums, int[] bucket, int len, int k, int index) {
            if(nums.length == index) {
                return true;
            }
            for(int i = 0; i < k; i++) {
                if(bucket[i] + nums[index] > len) {//装不下，就放到下一个桶中去
                    continue;
                }
                bucket[i] += nums[index];
                if(dfs(nums, bucket, len, k, index + 1)) {
                    return true;
                }
                bucket[i] -= nums[index];
                if(bucket[i] == 0) return false;//到了这儿，若为0，说明没有合适的值等于len
            }
            return false;
        }
    }

--------------------

## 二、火柴拼正方形 ##

> 题目描述：

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

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

![896caf530fcf48e6b5f873213d657df9.png][]

> 示例：

**输入:** matchsticks = \[1,1,2,2,2\]

**输出:** true

**解释:** 能拼成一个边长为2的正方形，每边两根火柴。

> 代码如下：

class Solution {
        //火柴拼正方形
        public boolean makesquare(int[] matchsticks) {
            int len = matchsticks.length;
            if(len < 4) { //特判:正方形有四条边
                return false;
            }
            //给所有火柴求和
            int sum = 0;
            for(int i = 0; i < matchsticks.length; i++) {
                sum += matchsticks[i];
            }
            if(sum % 4 != 0) { //特判：正方形有四条边
                return false;
            }
            //求出每一条边的长度
            int lenSide = sum / 4;
            //剪枝：降序排序更早触发回溯中的第一个continue
            Arrays.sort(matchsticks);
            //降序
            for(int i = 0, j = matchsticks.length - 1; i < j; i++, j--) {
                int tmp = matchsticks[i];
                matchsticks[i] = matchsticks[j];
                matchsticks[j] = tmp;
            }
            //四个桶
            int[] bucket = new int[4];
            return dfs(matchsticks, lenSide, bucket, 0);
        }
    
        private boolean dfs(int[] arr, int lenSide, int[] bucket, int index) {
            if(index == arr.length) {
                return true;
            }
            for(int i = 0; i < 4; i++) {
                if(arr[index] + bucket[i] > lenSide) {//桶装不下了
                    continue;
                }
                bucket[i] += arr[index];
                if(dfs(arr, lenSide, bucket, index + 1)) {
                    return true;
                }
                bucket[i] -= arr[index];
                if(bucket[i] == 0) {
                    return false;
                }
            }
            return false;
        }
    }

--------------------

![b1d1fd63e9074acf96133a60587ee04c.gif][]

[698. _k_ - _LeetCode]: https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/
[896caf530fcf48e6b5f873213d657df9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/4cd203eca01a4259a75b53ba764a5c4e.png
[b1d1fd63e9074acf96133a60587ee04c.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/5ea527c2928146b58f634cb92c42895b.gif