I am solving a problem Partition to K Equal Sum Subsets on LeetCode:

Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal. So, if Input: nums = [4,3,2,3,5,2,1], k = 4; Output: true.

The code I am referring is as below:

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;
    }
}

I don't quite follow the reason for break statement in the code above. My solution was very similar but without break (and the if and else clauses combined into one), but mine TLEs (times out), while this one (with a break) gets accepted with a good runtime.

What is the significance of the break statement here? Specifically, how does it speed things up?

Thanks!

CodePudding user response：

subsetSum[] contains "buckets" for which elements are placed during your depth-first search.

Consider what happens when there are multiple empty "buckets". It does not matter which of these empty "buckets" you place the current element into, as they are all theoretically identical.

Consider this example. Let's say subsetSum[] contains {1, 2, 0, 0, 0}. You want to place an element of value 5 into one of the "buckets".

If you place it such that the new subsetSum[] contains {1, 2, 0, 5, 0} as opposed to {1, 2, 5, 0, 0}, the two are effectively the same as the ordering of subsetSum[] is unimportant. However, if you do decide to calculate both, you are doubling your runtime at this branch. Combined, this can lead to an exponentially slower runtime.

The break statement is executed after the first "bucket" such that subsetSum[subsetIdx]==0. This means that in {1, 2, 0, 0, 0}, for example, we will never reach the state {1, 2, 0, 5, 0} as the loop has broken after trying {1, 2, 5, 0, 0}, preventing duplicate calculations and greatly speeding up runtime.