698. 划分为k个相等的子集:给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。

题目描述

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

示例 1:
  • 输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
  • 输出: True
  • 说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
示例 2:
  • 输入: nums = [1,2,3,4], k = 3
  • 输出: false
  • 提示:
    1 <= k <= len(nums) <= 16
    0 < nums[i] < 10000
    每个元素的频率在 [1,4] 范围内

思路

首先,找到当前数组的总和能不能被k整除

  • 能够被k整除的话,证明数组的数字总和能平均的分为k份
  • 不能的话,就直接返回false

返回false的情况

  1. 当前数组的总和不能被k整除
  2. 数组中最大的值等于数组求和后的平均值

使用桶的思想解决:借用他人的观点如下:

以数组为[10,10,10,7,7,7,7,7,7,6,6,6],分成3部分为例,
即分成3个桶,每个桶的和为30

排序后数组为[6,6,6,7,7,7,7,7,7,10,10,10],需要放在3个桶中,每个桶的和为30

第一层递归,末尾的10放在第一个桶中
|   |   |   |   |   |
|   |	|   |   |   |
|   |	|   |   |   |
|10 |	|   |   |   |
 ---	 ---	 ---
桶1      桶2      桶3

第二层和第三层递归,倒数第二个和倒数第三个10都放在桶1中
|   |   |   |   |   |
|10 |	|   |   |   |
|10 |	|   |   |   |
|10 |	|   |   |   |
 ---	 ---	 ---
桶1      桶2      桶3

第四层递归,倒数第一个7就不能放在桶1中了,因为30+7>30
所以放在桶2中
|   |   |   |   |   |
|10 |	|   |   |   |
|10 |	|   |   |   |
|10 |	|7  |   |   |
 ---	 ---	 ---
桶1      桶2      桶3

后续直到桶2中放了4个7,

|   |   |7  |   |   |
|10 |	|7  |   |   |
|10 |	|7  |   |   |
|10 |	|7  |   |   |
 ---	 ---	 ---
桶1      桶2      桶3

再有7就不能放到桶2中了,因为5*7>30
后续的2个7和2个6放到了桶3中

|   |   |7  |   |6  |
|10 |	|7  |   |6  |
|10 |	|7  |   |7  |
|10 |	|7  |   |7  |
 ---	 ---	 ---
桶1      桶2      桶3

这是第一个6这时没地方放了,因为放到任何一个桶中,都大于30
这时遍历3个桶,都没法放进去之后,返回false

然后递归返回,

递归返回到存放的倒数第二个6,倒数第二个6从桶3中出栈,但是没有桶4可以让倒数第二个6放进去了,
for循环直接结束了,同时返回false
同理,桶3中的元素会依次从桶3中出栈

然后桶2中的栈顶的7,会尝试放到桶3中,再递归下去,(剩余的数组元素为[6,6,6,7,7])
当然我们知道这种情况也是无解的,

|   |   |   |   |   |
|10 |	|7  |   |   |
|10 |	|7  |   |   |
|10 |	|7  |   |7  |
 ---	 ---	 ---
桶1      桶2      桶3

最终桶2中的元素,会全部依次出栈,此时数组中剩余的元素为[6,6,6,7,7,7,7,7,7]

|   |   |   |   |   |
|10 |	|   |   |   |
|10 |	|   |   |   |
|10 |	|   |   |   |
 ---	 ---	 ---
桶1      桶2      桶3

如果没有 if (groups[i] == 0) break; 这行代码

我们知道了桶2已经是空了,但是仍然会运行for循环,把倒数第一个位置的7,放到桶3中再次尝试,并继续递归下去
但是这样其实没有意义,因为桶2和桶3的地位是一样的,
这种情况也是无解的,所以可以剪枝

同样,桶1中的栈顶的2个10都会出栈,最终会平均分配到3个桶中,剩余的元素,也都会平均分配到每个桶中

|6  |   |6  |   |6  |
|7  |	|7  |   |7  |
|7  |	|7  |   |7  |
|10 |	|10 |   |10 |
 ---	 ---	 ---
桶1      桶2      桶3

最后一次递归的时候 row就是-1了,这时直接返回true

代码

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for(int i = 0; i < nums.length; i++){
            sum += nums[i];
        }
        if(sum % k != 0){
            return false;
        }
        //求出子集的和
        sum = sum / k;
        //排序 从小到大
        Arrays.sort(nums);
        //如果数组的最大值>target,证明有一个数是无法放入的,所以无法满足题意,直接返回false
        if(nums[nums.length - 1] > sum){
            return false;
        }
        //建立一个长度为k的桶
        int[] arr = new int[k];
        //将桶中的所有元素设置为子集的和,通过fill函数
        Arrays.fill(arr, sum);
        //从数组最后一个数开始进行递归
        return help(nums, nums.length - 1, arr, k);
    }
    //cur:当前的元素位置
    //arr:填满所求子集的和
    //k:所要获取的子集数目
    boolean help(int[] nums, int cur, int[] arr, int k){
        //已经遍历到了-1说明前面的所有数都正好可以放入桶里,那所有桶的值此时都为0,说明找到了结果,返回true
        if(cur < 0){
            return true;
        }
        //遍历k个桶
        for(int i = 0; i < k; i++){
            //如果正好能放下当前的数,或者放下当前的数后,还有机会继续放前面的数(剪枝)
            //arr[i] - nums[cur] >= nums[0]:条件成立是因为数组按从小到大排序,大于第一个就证明还可以继续存放数
            if(arr[i] == nums[cur] || (cur > 0 && arr[i] - nums[cur] >= nums[0])){
                //放当前的数到桶i里
                arr[i] -= nums[cur];
                //开始放下一个数
                if(help(nums, cur - 1, arr, k)){
                    return true;
                }
                //这个数不该放在桶i中
                //从桶中拿回当前的数
                arr[i] += nums[cur];
            }
        }
        return false;
    }
}

代码说明

这次看注释吧,注释写的很清楚;

首先判断该数组所要求的子集是否能够出现,有两种情况不能出现:

  1. 当前数组的总和不能被k整除
  2. 数组中最大的值等于数组求和后的平均值

如果判断能够出现的话,就需要使用桶进行运算

  1. 遍历每一个桶
  2. 每一个桶能够存放的数据是之前所求的平均值
  3. 使用一个方法递归,
上一篇:ASP.NET MVC3 Razor视图引擎-基础语法


下一篇:grep命令的用法