当数组元素的回溯零速度时，如何破坏零速度？

Question

我正在解决一个问题 k super sum sumsets 在leetcode上：

给定整数数组和一个整数k，如果可以将此数组分为k非空的子集，其总和都相等。因此，如果输入：nums = [4,3,2,3,5,2,1]，k = 4;输出：true。

代码i是参考如下：

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（以及 and else等级组合成一个），但是矿山（times out），而这个（带有break）的运行时被接受。

break语句在这里有什么意义？具体来说，它如何加快速度？

谢谢！

Answer 1

subsetsum []包含在深度优先搜索期间放置元素的“存储桶”。

考虑有多个空的“桶”时会发生什么。您将当前元素放入哪个空的“存储桶”中，因为它们在理论上都是相同的。

考虑这个示例。假设subsetum []包含{1，2，2，0，0，0，0}。您想将价值5的元素放入其中一个“存储桶”中。

如果将其放置以使新的subsetum []包含{1，2，2，0，5，0}，而不是{1，2，2，5， 0，0}，两者实际上与subsetsum []的排序相同。但是，如果您确实决定两者都会计算两者，则在此分支机构将运行时间加倍。结合在一起，这可能会导致成倍缓慢的运行时。

break语句是在第一个“桶”之后执行的，因此subsetsum [subsetidx] == 0。这意味着在{1、2、0、0、0、0}中，我们将永远不会达到状态{1，2，2，2，0，5，0}由于尝试{1、2、5、0、0}之后，循环已经断开，因此阻止了重复的计算并大大加快了运行时。