698. Partition to K Equal Sum Subsets
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
（最近做了挺多的DFS题目，这道题没做出来 o.O||，还是菜啊 ）做法来自 小f讲解。这道题目本以为会有其他的方法，最后也只能不断暴力递归求解。递归时先建立指定个数的桶，每个桶内数字总和是相等的。partation方法的含义是每个下标在这几个桶内都能够放下，只要满足这个条件即返回成功。只要找到一种可行方式即可。
求总和时用了Arrays.stream().sum()方法结果耗时 47ms，换手动计算变成 13ms。所以数据集有限的情况下，算法题还是谨慎用流。
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
| public boolean canPartitionKSubsets(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) {
return false;
}
int sum = sum(nums);
if (sum % k != 0) {
return false;
}
Arrays.sort(nums);
int subSum = sum / k;
int index = nums.length - 1;
if (nums[index] > subSum) {
return false;
}
int subNum = k;
while (index >= 0 && nums[index] == subSum) {
index--;
subNum--;
}
return partition(nums, subSum, index, new int[subNum]);
}
private boolean partition(int[] num, int target, int index, int[] subSet) {
if (index < 0) {
return true;
}
for (int i = 0; i < subSet.length; i++) {
if (subSet[i] + num[index] <= target) {
subSet[i] += num[index];
if (partition(num, target, index - 1, subSet)) {
return true;
}
subSet[i] -= num[index];
}
}
return false;
}
private int sum(int[] array) {
int sum = 0;
for (int i : array) {
sum += i;
}
return sum;
}
|
