# this code is accepted and run fast(12ms), but don't know how to prove it.

• Hi all

Although this code is accepted and run fast(12ms), I cannot prove its correctness.

My idea of grouping is that
I start from largest available item and use backtracking to find the candidates.
Once the sum of those candidates equals to the average, then stop the process. And I repeat the whole process exactly K times.

My question is that is this kind of greedy strategy actually work or it just fits current test cases?

Here is my code.

``````public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int n : nums) {
sum += n;
}
if(sum % k != 0)
return false;

int target = sum / k;
Arrays.sort(nums);

boolean[] taken = new boolean[nums.length];
for(int i=0;i<k;i++) {
if(bt(nums, taken, target, 0) == false)
return false;
}

return true;
}

boolean bt(int[] nums, boolean[] taken, int target, int sum) {
if(target == sum) {
return true;
}

for(int i=nums.length-1;i>=0; i--) {
if(taken[i])
continue;

if(sum + nums[i] > target)
return false;

taken[i] = true;
boolean ret = bt(nums, taken, target, sum + nums[i]);
if(ret == true)
return true;
taken[i] = false;
}

return false;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.