Problem: 698. 划分为k个相等的子集
👨🏫 参考题解
🍻 球选桶
class Solution {public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i = 0; i < nums.length; i++)sum += nums[i];if (sum % k != 0)return false;int target = sum / k;// 排序优化Arrays.sort(nums);int l = 0, r = nums.length - 1;while (l <= r) {int temp = nums[l];nums[l] = nums[r];nums[r] = temp;l++;r--;}return backtrack(nums, 0, new int[k], k, target);}private boolean backtrack(int[] nums, int index, int[] bucket, int k, int target) {// 结束条件优化if (index == nums.length)return true;for (int i = 0; i < k; i++) {// 优化点二if (i > 0 && bucket[i] == bucket[i - 1])continue;// 剪枝if (bucket[i] + nums[index] > target)continue;bucket[i] += nums[index];if (backtrack(nums, index + 1, bucket, k, target))return true;bucket[i] -= nums[index];}return false;}
}
🍻 桶选球
class Solution {public boolean canPartitionKSubsets(int[] nums, int k) {int sum = 0;for (int i = 0; i < nums.length; i++)sum += nums[i];if (sum % k != 0)return false;int target = sum / k;// 排序优化Arrays.sort(nums);int l = 0, r = nums.length - 1;while (l <= r) {int temp = nums[l];nums[l] = nums[r];nums[r] = temp;l++;r--;}boolean[] used = new boolean[nums.length];return backtrack(nums, 0, new int[k+1], k, target,used);}private boolean backtrack(int[] nums, int start, int[] bucket, int k, int target, boolean[] used) {// k 个桶均装满if (k == 0)return true;// 当前桶装满了，开始装下一个桶if (bucket[k] == target) {// 注意：桶从下一个开始；球从第一个开始return backtrack(nums, 0, bucket, k - 1, target, used);}// 第 k 个桶开始对每一个球选择进行选择是否装入for (int i = start; i < nums.length; i++) {// 如果当前球已经被装入，则跳过if (used[i])continue;// 如果装入当前球，桶溢出，则跳过if (bucket[k] + nums[i] > target)continue;// 装入 && 标记已使用bucket[k] += nums[i];used[i] = true;// 开始判断是否选择下一个球// 注意：桶依旧是当前桶；球是下一个球// 注意：是 i + 1if (backtrack(nums, i + 1, bucket, k, target, used))return true;// 拿出 && 标记未使用bucket[k] -= nums[i];used[i] = false;}// 如果所有球均不能使所有桶刚好装满return false;}
}
