Medium
這題原來(lái)的解法不是很好懂设联，有位拿到google offer的前輩說(shuō)解法最重要的是“自己覺(jué)得好懂 + 面試當(dāng)場(chǎng)能解釋清楚”的式塌。 我覺(jué)得很對(duì)贯被，自己做得最順的可能既不是最naive的也不是最優(yōu)化的，但可以先用自己覺(jué)得最理解的方法做，再一步步學(xué)會(huì)優(yōu)化即可庆冕。
一開(kāi)始先算出來(lái)每分的和是多少，解決一些可以盡早判斷t,f的情況劈榨。然后sort访递，如果最小的都比每分大，肯定false. 從后往前遍歷去跳過(guò)那些本身就等于每分subsum的元素同辣。比如[1,5,5,11]里面的11. 跳過(guò)的時(shí)候beginIndex--,k--. 然后新建一個(gè)size = k的int[] 來(lái)存subsets拷姿，每個(gè)index對(duì)應(yīng)的數(shù)就是每一分現(xiàn)在的sum.
helper method需要int[k] subset, int[] nums, int subSum, int index做參數(shù)惭载。這個(gè)index就是從后遍歷到現(xiàn)在的那個(gè)index。我們可以進(jìn)入helper method就判斷這個(gè)index是不是小于0响巢，如果是的話描滔，說(shuō)明我們已經(jīng)遍歷完所有的nums元素，直接return true踪古。 然后我們選現(xiàn)在的這個(gè)selected數(shù)含长，讓它嘗試加入到當(dāng)前subsets里的每一組。如果某一組加了之后可以partition成功伏穆，就返回true. 如果不能拘泞，就backtracking.
畫(huà)一畫(huà)recursion tree 再分析一下時(shí)間空間復(fù)雜度：
什么情況canPartition會(huì)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 subSum = sum / k;
Arrays.sort(nums);
if (nums[0] > subSum){
return false;
}
int beginIndex = nums.length - 1;
while (beginIndex >= 0 && nums[beginIndex] == subSum){
beginIndex--;
k--;
}
return canPartition(nums, subSum, new int[k], beginIndex);
}
private boolean canPartition(int[] nums, int subSum, int[] subsets, int index){
if (index < 0){
return true;
}
int selected = nums[index];
for (int i = 0; i < subsets.length; i++){
if (subsets[i] + selected <= subSum){
subsets[i] += selected;
if (canPartition(nums, subSum, subsets, index - 1)){
return true;
}
subsets[i] -= selected;
}
}
return false;
}
}
