【LeetCode】第698题：将一个整数数组划分为K个相等的子集问题（字节跳动面试题）

今天药忘吃喽~ 2021-12-14 05:41 211阅读 0赞

最近看面经，有人在字节跳动的面试中，手写这道题，但是发现是 LeetCode 上的原题，所以记录下来。

> **题目：给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等**。
> 
> 示例 1：
> 
> 输入： nums = \[4, 3, 2, 3, 5, 2, 1\], k = 4  
> 输出： True  
> 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。  
>  
> 
> 注意:
> 
> 1 <= k <= len(nums) <= 16  
> 0 < nums\[i\] < 10000

*  ###  分析 ###

**前提：**需要先明确一个问题，一个数组能够划分出 k 个和相等子集的前提是：**这个数组的平均数必须是整数**。

**典型的递归问题**：现在总的数组中找到一个子集，再在剩下的数组元素中找到一个子集...直到所有子集都找到，结束递归。

**求解步骤：**

1、先求出数组的平均数 avg，如果平均数 avg 不为整数，也就是说数组的数字总和不能平均的分为 k 份，那么直接返回 false；

2、创建一个布尔数组 flag，用来记录 nums 数组中数字的状态（已用还是未用）。 temp 的作用是记录当前子集的数字总和，temp 初始为 avg ，当 temp 等于 0 时，当前这个子集也就可以确定了。index 是用来记录遍历数组时从哪个位置开始遍历，以防将前面的数字重新计算。

3、当 temp = 0 的时候，也就是新一个子集求解完，那么继续求解下一个子集，k - 1，temp 重新置为 avg；当 temp ！= 0 时，就是子集还未求解完，那么继续求解子集，继续从数组中取数字，递归求解。

4、当 k 个子集全部求解完，返回 true，如果一直求解不出，则返回 false。

*  ## 代码 ##

public class PartitionSubSets_698 {
    
        public static boolean canPartitionKSubSets(int[] nums, int k){
            int sum = 0;
            int len = nums.length;
            for(int i = 0; i < len; i++){
                sum += nums[i];
            }
    
            if(sum % k != 0){
                // 如果平均数不是整数，直接返回false
                return false;
            }
    
            int avg = sum / k;
            // 用于记录数组中的数据是否已经被使用，防止重复使用
            boolean[] flag = new boolean[len];
            return help(nums, flag, avg, k, avg, 0);
        }
    
        /**
         * 判断能否将数组nums划分为k个和相等的子集
         * @param nums ：数组
         * @param flag ：使用标记
         * @param avg ： 平均数
         * @param k ：k 个子集
         * @param temp ：也是平均数，这里用作记录子集的综合，等于0时，当前子集就确定了
         * @param index ：记录遍历数组时从哪个位置开始遍历，以防将前面的数字重新计算
         */
        public static boolean help(int[] nums, boolean[] flag, int avg, int k, int temp, int index){
            if(k == 0){
                // 说明已经k个子集都已经划分完成
                return true;
            }
            // temp等于0说明当前子集求解完毕，继续求解下一个子集，k-1，temp重置为avg，下标index也重置为0
            if(temp == 0){
                return help(nums, flag, avg, k - 1, avg, 0);
            }
    
            // 当前子集划分未完成
            for(int i = index; i < nums.length; i++){
                if(flag[i] == true){
                    // 如果当前数字已经被使用了，就不能再次使用了，只能使用一次
                    continue;
                }
                flag[i] = true;  // 使用
                // 递归调用子过程，父过程是否为true，取决于子过程的结果
                if(temp - nums[i] >= 0 && help(nums, flag, avg, k, temp - nums[i], index + 1)){
                    return true;
                }
                // 如果nums[i]不能使当前子集划分成功，需要释放掉，下次划分还可以使用
                flag[i] = false;
            }
            return false;
        }
    
        public static void main(String[] args) {
            int[] nums1 = {4, 3, 2, 3, 5, 2, 1};
            int[] nums2 = {4, 3, 2, 3, 5, 2, 2};
            System.out.println(canPartitionKSubSets(nums1, 4));
            System.out.println(canPartitionKSubSets(nums2, 4));
        }
    }

![20190708104854972.png][]

备注：可能做完这题会有一种担心：会不会存在一种情况，本来数组是可以等和划分成 k 份的，但是由于存在先后选择的问题，可能绕过了正好可以等和划分的组合。但是其实你认真想一下，再纸上画一画，分析下，应该是不存在这种情况的。因为划分成功的子集都是平均数，剩下的还是同样的子集问题，所以典型的递归问题。

[20190708104854972.png]: /images/20211213/cb70a0d2a4324074950110cb8424104d.png