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

2024-01-20 23:08:04

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. 结语

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

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