Medium
L家的tag题，之前contest好像是做过但没有做出来当时，这道题看了答案然后写出了一个及其奇怪的bug.
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for (int num : nums){
sum += num;
}
if (sum % k != 0){
return false;
}
int subSum = sum / k;
Arrays.sort(nums);
if (nums[nums.length - 1] > subSum){
return false;
}
int beginIndex = nums.length - 1;
while (beginIndex >= 0 && nums[beginIndex] == subSum){
beginIndex--;
k--;
}
return canPartition(new int[k], nums, subSum, beginIndex);
}
private boolean canPartition(int[] subsets, int[] nums, int target, int index){
if (index < 0){
return true;
}
int curtNum = nums[index];
for (int i = 0; i < subsets.length; i++){
if (subsets[i] + curtNum <= target){
subsets[i] += curtNum;
if (canPartition(subsets, nums, target, index - 1)){
return true;
}
subsets[i] -= curtNum;
}
}
return false;
}
}
