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


  • 0
    W

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

Log in to reply
 

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