# How does 'break'ing when array element is zero speed up backtracking?

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

### >Solution :

`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.