题目描述
给定一个整数数组 nums 和一个正整数 k,找出是否有可能把这个数组分成 k 个非空子集,其总和都相等。
解题思路
1. 思路分析
把装有 n 个数字的数组 nums 分成 k 个和相同的集合,可以想象将 n 个数字分配到 k 个「桶」里,最后这 k 个「桶」里的数字之和要相同。
- 如果切换到这 n 个数字的视角,每个数字都要选择进入到 k 个桶中的某一个。
- 如果切换到这 k 个桶的视角,对于每个桶,都要遍历 nums 中的 n 个数字,然后选择是否将当前遍历到的数字装进自己这个桶里。
2. 递归遍历数组
void traverse(int[] nums, int index) {
if (index == nums.length) {
return;
}
System.out.println(nums[index]);
traverse(nums, index + 1);
}
代码
static boolean canPartitionKSubsets(int[] nums, int k) {
if (k > nums.length) {
return false;
}
int sum = 0;
for (int v : nums) {
sum += v;
}
if (sum % k != 0) {
return false;
}
int[] bucket = new int[k];
int target = sum / k;
return backtrack(nums, 0, bucket, target);
}
static boolean backtrack(int[] nums, int index, int[] bucket, int target) {
if (index == nums.length) {
for (int i = 0; i < bucket.length; i++) {
// 检查所有桶的数字之和是否都是 target
if (bucket[i] != target) {
return false;
}
}
// nums 成功平分成 k 个子集
return true;
}
// 穷举 nums[index] 可能装入的桶
for (int i = 0; i < bucket.length; i++) {
// 剪枝,桶装装满了
if (nums[index] + bucket[i] > target) {
continue;
}
// 将 nums[index] 装入 bucket[i]
bucket[i] += nums[index];
// 递归穷举下一个数字的选择
if (backtrack(nums, index + 1, bucket, target)) {
return true;
}
// 撤销选择
bucket[i] -= nums[index];
}
// nums[index] 装入哪个桶都不行
return false;
}
Q.E.D.