我正在解決LeetCode 上K 等和子集的磁區問題：
給定一個整數陣列 nums 和一個整數 k，如果可以將該陣列劃分為 k 個和都相等的非空子集，則回傳 true。所以，如果輸入：nums = [4,3,2,3,5,2,1], k = 4; 輸出：真。
我指的代碼如下：
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 subsetSum[] = new int[k];
return canPartitionKSubsets(nums,0,subsetSum,k,sum);
}
private boolean canPartitionKSubsets(int nums[] , int idx , int subsetSum[] , int k , int sum){
if(idx==nums.length){
int sumObtained = subsetSum[0];
for(int subsetIdx = 1;subsetIdx<k;subsetIdx ){
if(subsetSum[subsetIdx]!=sumObtained) return false;
}
return true;
}
for(int subsetIdx=0;subsetIdx<k;subsetIdx ){
if(subsetSum[subsetIdx]>(sum/k)) return false;
}
for(int subsetIdx=0;subsetIdx<k;subsetIdx ){
if(subsetSum[subsetIdx]==0){
subsetSum[subsetIdx] = nums[idx];
boolean canPartition = canPartitionKSubsets(nums,idx 1,subsetSum,k,sum);
if(canPartition) return true;
subsetSum[subsetIdx] = 0;
break; //-------> why??
}else{
subsetSum[subsetIdx] = nums[idx];
boolean canPartition = canPartitionKSubsets(nums,idx 1,subsetSum,k,sum);
if(canPartition) return true;
subsetSum[subsetIdx]-= nums[idx];
}
}
return false;
}
}
我不太理解break上面代碼中宣告的原因。我的解決方案非常相似，但沒有break（并且ifandelse子句合并為一個），但是我的 TLE（超時），而這個（帶有 a break）在良好的運行時被接受。
這里的宣告有什么意義break？具體來說，它如何加快速度？
謝謝！
uj5u.com熱心網友回復：
subsetSum[]包含在深度優先搜索期間放置元素的“桶”。
考慮當有多個空“桶”時會發生什么。將當前元素放入這些空“桶”中的哪個并不重要，因為它們在理論上都是相同的。
考慮這個例子。比方說subsetSum[]包含{1, 2, 0, 0, 0}。您想將價值元素5放入“桶”之一。
如果您將其放置為 new subsetSum[]contains{1, 2, 0, 5, 0}而不是{1, 2, 5, 0, 0}，則兩者實際上是相同的，因為subsetSum[]order 并不重要。但是，如果您決定同時計算兩者，那么您在這個分支上的運行時間就會增加一倍。結合起來，這可能會導致運行時間呈指數級下降。
該break陳述句在第一個“桶”之后執行，這樣subsetSum[subsetIdx]==0. 這意味著，{1, 2, 0, 0, 0}例如，{1, 2, 0, 5, 0}在嘗試后，我們將永遠不會達到回圈中斷的狀態{1, 2, 5, 0, 0}，從而防止重復計算并大大加快運行時間。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489528.html