Java: standard backtracking solution, 21ms


  • 0
    E
    public boolean canPartitionKSubsets(int[] nums, int k) {
            int sum = 0;
            for(int num : nums) {
                sum += num;
            }
            if(sum % k != 0) {
                return false;
            }
            int target = sum / k;
            return helper(target, nums, 0, k, 0);
        }
    
        private boolean helper(int target, int[] nums, int preSum, int remain, int start) {
            if(remain == 1) {
                return true;
            }
            if(preSum == target) {
                return helper(target, nums, 0, remain - 1, 0);
            }
          
            for(int i = start; i < nums.length; i++) {
                if(helper(target, nums, preSum + nums[i], remain, i + 1)) {
                    return true;
                }
            }
            return false;
        }
    

  • 0
    D

    add accumulation sum check can speed it up. if sorted array is [1, 2, 3, 4], then accumulation sum [1, 3, 6, 10], check this sum with preSum

                if(!visit[i]) {
                     if (target - preSum > accuSums[i]) {
                         return false;
                     }

  • 1
    D

    you're not storing whether number has used or not, this case'll fail:

    [5,3,1]
    3
    

    but again the question didn't contain this kind of case.


  • 0
    E

    @D3Hunter Yes, u are right.

    Actually, in contest, I sort the nums and add a if statement

    if(nums[nums.length - 1] > target)  return false;
    

  • 0
    D

    @element.radium
    that check is not enough, check this:

    [2,3,3,2,2]
    3
    

  • 0
    E

    @D3Hunter Thank you, I will revise it to a right solution!

    Many many thanks


Log in to reply
 

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