698. 划分为k个相等的子集

1. 题目

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

2. 示例

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

3. 提示

  • 1 <= k <= len(nums) <= 16
  • 0 < nums[i] < 10000

4. 题解

对于划分问题,大多数都可以用动态规划和回溯。

该题的边界条件是均分子集。

那么我们将每个子集看成一个桶,然后回溯往桶里放数。

5.实现

 1 public class CanPartitionKSubsetsA {
 2     public boolean canPartitionkSubsets(int[] nums, int k) {
 3         int sum = 0;
 4         for(int num : nums) {
 5             sum += num;
 6         }
 7         // 不能均分为k个子集
 8         if(sum % k != 0) return false;
 9         sum /= k;
10         if(sum < nums[nums.length - 1]) return false;
11         Arrays.sort(nums);
12         // 定义k个桶,每个桶容量为sum
13         int[] bucket = new int[k];
14         Arrays.fill(bucket, sum);
15         // 回溯
16         return backTrack(nums, bucket, nums.length - 1);
17     }
18     public boolean backTrack(int[] nums, int[] bucket, int cur) {
19         // 从后往前找,能将第一个放进去,说明能均分为k个子集
20         if(cur < 0) return true;
21         // 对桶进行遍历,装每一个桶
22         for(int i = 0; i < bucket.length; i++) {
23             // 当前数刚好能放进桶或者放了该数后,还能继续放入数
24             if(bucket[i] == nums[cur] || (bucket[i] - nums[cur] >= nums[0])) {
25                 // 当前数放入i桶, 如果能让得到均分子集,那么完毕。
26                 bucket[i] -= nums[cur];
27                 if(backTrack(nums, bucket, cur - 1)) return true;
28                 // 当前数放入i桶后,不能得到均分子集,取出当前数放入后续的桶
29                 bucket[i] += nums[cur];
30             }
31             //注意,不加,[1,3,4,4,4,10,10,10,10,10,10,10,10,10,10,10]12用例超时
32             if(bucket[i] == 0) break;
33 
34         }
35         return false;
36     }
37 
38     public static void main(String[] args) {
39         int[] nums = {4, 3, 2, 3, 5, 2, 1};
40         int k = 4;
41         System.out.println(new CanPartitionKSubsetsA().canPartitionkSubsets(nums, k));
42     }
43 }

6.  结语

  努力去爱周围的每一个人,付出,不一定有收获,但是不付出就一定没有收获! 给街头卖艺的人零钱,不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)!

  如果客官喜欢小生的园子,记得关注小生哟,小生会持续更新(#^.^#)(#^.^#)。

698. 划分为k个相等的子集

上一篇:flutter环境配置遇到的一些坑


下一篇:element-ui 生成动态表单