友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
698. Partition to K Equal Sum Subsets
Given an array of integers nums and a positive integer k, find whether it’s possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
Output: True
Explanation: It's possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.Note:
-
1 ⇐ k ⇐ len(nums) ⇐ 16. -
0 < nums[i] < 10000.
思路分析
球视角
-
一刷（超时）
-
一刷（优化）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* 第一版：超时，通过 150/163 个测试用例
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-10 17:23:46
*/
public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length == 0 || nums.length < k) {
return false;
}
// 总和不能整除，肯定无法均分
int sum = Arrays.stream(nums).sum();
if (sum % k != 0) {
return false;
}
boolean[] used = new boolean[nums.length];
int[] bucket = new int[k];
int target = sum / k;
return backtrack(nums, used, 0, bucket, target);
}
private boolean backtrack(int[] nums, boolean[] used, int start, int[] bucket, int target) {
// 遍历完了所有数组
if (start == nums.length) {
return true;
}
for (int i = 0; i < bucket.length; i++) {
// 剪枝：如果该桶总和大于平均值，则跳过
if (target < nums[start] + bucket[i]) {
continue;
}
if (used[start]) {
continue;
}
used[start] = true;
bucket[i] += nums[start];
if (backtrack(nums, used, start + 1, bucket, target)) {
return true;
}
bucket[i] -= nums[start];
used[start] = false;
}
return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* 第一版：超时，通过 150/163 个测试用例
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-10 17:53:39
*/
public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length == 0 || nums.length < k) {
return false;
}
// 总和不能整除，肯定无法均分
int sum = Arrays.stream(nums).sum();
if (sum % k != 0) {
return false;
}
int target = sum / k;
// 排序：逆序先放大元素，这样减少回溯的可能和次数
Arrays.sort(nums);
for (int l = 0, r = nums.length - 1; l < r; l++, r--) {
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
// 最大元素大于平均值，也不可能平分，直接返回
if (target < nums[0]) {
return false;
}
int[] bucket = new int[k];
return backtrack(nums, 0, bucket, target);
}
private boolean backtrack(int[] nums, int start, int[] bucket, int target) {
// 遍历完数组内所有的数字，那么就成功
if (start == nums.length) {
return true;
}
for (int i = 0; i < bucket.length; i++) {
// 剪枝：如果两个桶的值一样，只要做一个尝试即可
// 这里也包含了：第一个数字放在第一个桶的优化点
// 解释：最初始时，所有的桶都是0，在执行完第一个桶后，
// 由于回溯一加一减，所有的桶还是0，后面的桶就直接跳过了。
if (0 < i && bucket[i - 1] == bucket[i]) {
continue;
}
// 剪枝：如果该桶总和大于平均值，则跳过
if (target < nums[start] + bucket[i]) {
continue;
}
bucket[i] += nums[start];
if (backtrack(nums, start + 1, bucket, target)) {
return true;
}
bucket[i] -= nums[start];
}
return false;
}
