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


  • 0
    P

    Can you explain the time Complexity?


  • 0
    S

    Just ran the code pasted above. Doesn't seem like it works right now. Can you please update?


Log in to reply
 

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