for (int index = 0; index < nums.length; index++) {
System.out.println(nums[index]);
}
递归遍历数组你会不会？其实也很简单：
void traverse(int[] nums, int index) {
if (index == nums.length) {
return;
}
System.out.println(nums[index]);
traverse(nums, index + 1);
}
只要调用 traverse(nums, 0)，和 for 循环的效果是完全一样的。
那么回到这道题，以数字的视角，选择 k 个桶，用 for 循环写出来是下面这样：
// k 个桶（集合），记录每个桶装的数字之和
int[] bucket = new int[k];
// 穷举 nums 中的每个数字
for (int index = 0; index < nums.length; index++) {
// 穷举每个桶
for (int i = 0; i < k; i++) {
// nums[index] 选择是否要进入第 i 个桶
// ...
}
}
如果改成递归的形式，就是下面这段代码逻辑：
// k 个桶（集合），记录每个桶装的数字之和
int[] bucket = new int[k];
// 穷举 nums 中的每个数字
void backtrack(int[] nums, int index) {
// base case
if (index == nums.length) {
return;
}
// 穷举每个桶
for (int i = 0; i < bucket.length; i++) {
// 选择装进第 i 个桶
bucket[i] += nums[index];
// 递归穷举下一个数字的选择
backtrack(nums, index + 1);
// 撤销选择
bucket[i] -= nums[index];
}
}
虽然上述代码仅仅是穷举逻辑，还不能解决我们的问题，但是只要略加完善即可：
// 主函数
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;
// k 个桶（集合），记录每个桶装的数字之和
int[] bucket = new int[k];
// 理论上每个桶（集合）中数字的和
int target = sum / k;
// 穷举，看看 nums 是否能划分成 k 个和为 target 的子集
return backtrack(nums, 0, bucket, target);
}
// 递归穷举 nums 中的每个数字
boolean backtrack(
int[] nums, int index, int[] bucket, int target) {
if (index == nums.length) {
// 检查所有桶的数字之和是否都是 target
for (int i = 0; i < bucket.length; i++) {
if (bucket[i] != target) {
return false;
}
}
// nums 成功平分成 k 个子集
return true;
}
// 穷举 nums[index] 可能装入的桶
for (int i = 0; i < bucket.length; i++) {
// 剪枝，桶装装满了
if (bucket[i] + nums[index] > 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;
}
现在 k 号桶正在思考是否应该把 nums[start] 这个元素装进来；目前 k 号桶里面已经装的数字之和为 bucket；used 标志某一个元素是否已经被装到桶中；target 是每个桶需要达成的目标和。
根据这个函数定义，可以这样调用 backtrack 函数：
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;
boolean[] used = new boolean[nums.length];
int target = sum / k;
// k 号桶初始什么都没装，从 nums[0] 开始做选择
return backtrack(k, 0, nums, 0, used, target);
}
实现 backtrack 函数的逻辑之前，再重复一遍，从桶的视角：
1、需要遍历 nums 中所有数字，决定哪些数字需要装到当前桶中。
2、如果当前桶装满了（桶内数字和达到 target），则让下一个桶开始执行第 1 步。
下面的代码就实现了这个逻辑：
boolean backtrack(int k, int bucket,
int[] nums, int start, boolean[] used, int target) {
// base case
if (k == 0) {
// 所有桶都被装满了，而且 nums 一定全部用完了
// 因为 target == sum / k
return true;
}
if (bucket == target) {
// 装满了当前桶，递归穷举下一个桶的选择
// 让下一个桶从 nums[0] 开始选数字
return backtrack(k - 1, 0 ,nums, 0, used, target);
}
// 从 start 开始向后探查有效的 nums[i] 装入当前桶
for (int i = start; i < nums.length; i++) {
// 剪枝
if (used[i]) {
// nums[i] 已经被装入别的桶中
continue;
}
if (nums[i] + bucket > target) {
// 当前桶装不下 nums[i]
continue;
}
// 做选择，将 nums[i] 装入当前桶中
used[i] = true;
bucket += nums[i];
// 递归穷举下一个数字是否装入当前桶
if (backtrack(k, bucket, nums, i + 1, used, target)) {
return true;
}
// 撤销选择
used[i] = false;
bucket -= nums[i];
}
// 穷举了所有数字，都无法装满当前桶
return false;
}