题目描述
划分为k个相等的子集给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。
提示:
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
样例
示例 1:
输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4
输出: True
说明: 有可能将其分成 4 个子集(5),(1,4),(2,3),(2,3)等于总和。
算法
(DFS+剪枝) O(k * 2^n)
本题目从数据范围1 <= k <= len(nums) <= 16,基本上可以判定可以用搜索来做,
思路类似LeetCode 473. Matchsticks to Square,
参考y总思路:
四种剪枝方法:
1. 从大到小枚举所有边
2. 每条边的内部长度从大到小填
3. 如果当前填充失败,那么跳过接下来所有相同长度的
4. 如果当前填充失败,并且是当前边的第一个,则直接剪掉当前分支
5. 如果当前填充失败,并且是当前边的最后一个,则直接剪掉当前分支
Java 代码
public class Solution {
boolean[] used;
public boolean canPartitionKSubsets(int[] nums, int k) {
int n = nums.length;
if (n == 0 || k == 0 || n < k) {
return false;
}
used = new boolean[n];
nums = Arrays.stream(nums).boxed().sorted(Comparator.reverseOrder()).mapToInt(Integer::intValue).toArray();
int sum = Arrays.stream(nums).sum();
if (sum % k != 0) {
return false;
}
return dfs(nums, k, 0,0 , sum / k);
}
/**
* 递归函数
* @param nums 原始数组
* @param k k 个非空子集
* @param index 当前枚举的边
* @param currLen 当前枚举的边的长度
* @param singleSize 每条边的标准长度,不能超过
* @return
*/
private boolean dfs(int[] nums, int k, int index, int currLen, int singleSize) {
// 一个边完成了
if (currLen == singleSize) {
index++;
currLen = 0;
}
// 完成所有边的枚举
if (index == k) {
return true;
}
// 尝试所有数字
for (int i = 0; i < nums.length; i++) {
if (!used[i] && currLen + nums[i] <= singleSize) {
used[i] = true;
if (dfs(nums, k, index, currLen + nums[i], singleSize)) {
return true;
}
used[i] = false;
// 第三个剪枝,如果当前填充失败,那么跳过接下来所有相同长度的
while (i + 1 < nums.length && nums[i + 1] == nums[i]) {
i++;
}
// 第四个剪枝,如果当前填充失败,并且是当前边的第一个,则直接剪掉当前分支
if (currLen == 0) {
return false;
}
// 第五个剪枝,如果当前填充失败,并且是当前边的最后一个,则直接剪掉当前分支
if (currLen + nums[i] == singleSize) {
return false;
}
}
}
return false;
}
}