package leetcode;

/**
 * https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
 */
public class Problem698 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        // TODO
        return false;
    }

    private static boolean canPartition(int[] nums, int k, int idx) {
        if (k == 0 && idx == nums.length) {
            return true;
        }
        if (k == 0 && idx < nums.length) {
            return false;
        }
        for (int i = idx; i < nums.length; i++) {
            // TODO
        }
        return false;
    }

    public static void main(String[] args) {
        Problem698 prob = new Problem698();
        System.out.println(prob.canPartitionKSubsets(new int[]{4, 3, 2, 3, 5, 2, 1}, 4)); // true
        System.out.println(prob.canPartitionKSubsets(new int[]{5, 3, 2, 3, 4, 2, 1}, 4)); // true
    }
}

@@ -186,36 +186,301 @@
     
-// TODO%0A        return false
+int sum = 0;%0A        for (int i = 0; i %3C nums.length; i++) %7B%0A            sum += nums%5Bi%5D;%0A        %7D%0A        int sub = sum / k;%0A        if (sum %25 k != 0) %7B%0A            return false;%0A        %7D%0A        Boolean%5B%5D%5B%5D memo = new Boolean%5Bk + 1%5D%5Bsub + 1%5D;%0A        return canPartition(nums, k, sub, memo)
 ;%0A  
@@ -547,19 +547,37 @@
  k, int 
-idx
+sub, Boolean%5B%5D%5B%5D memo
 ) %7B%0A    
@@ -576,33 +576,35 @@
 ) %7B%0A        if (
-k
+sub
  == 0 && idx == 
@@ -600,26 +600,14 @@
  && 
-idx
+k
  == 
-nums.length
+0
 ) %7B%0A
@@ -659,33 +659,24 @@
  (k 
-=
+%3C
 = 0 
-&& idx %3C nums.length
+%7C%7C sub %3C= 0
 ) %7B%0A
@@ -703,32 +703,142 @@
 alse;%0A        %7D%0A
+        if (memo%5Bk%5D%5Bsub%5D != null) %7B%0A            return memo%5Bk%5D%5Bsub%5D;%0A        %7D%0A        boolean found = false;%0A
         for (int
@@ -846,11 +846,9 @@
 i = 
-idx
+0
 ; i 
@@ -885,25 +885,104 @@
     
-// TODO%0A        %7D
+found %7C= canPartition(nums, k - 1, sub - nums%5Bi%5D, memo);%0A        %7D%0A        memo%5Bk%5D%5Bsub%5D = found;
 %0A   
@@ -990,28 +990,28 @@
     return f
-alse
+ound
 ;%0A    %7D%0A%0A   
@@ -1096,16 +1096,18 @@
 m698();%0A
+//
         
@@ -1192,24 +1192,26 @@
 )); // true%0A
+//
         Syst
@@ -1296,16 +1296,316 @@
 // true%0A
+//        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B5, 3, 2, 3, 4, 2, 2%7D, 4)); // false%0A//        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B1, 2, 3, 4%7D, 3)); // false%0A        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B1, 1, 1, 1, 1, 1, 1, 1, 1, 1%7D, 5)); // true%0A
     %7D%0A%7D%0A

Update problem 698