package leetcode;

/**
 * https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
 */
public class Problem698 {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int sub = sum / k;
        if (sum % k != 0) {
            return false;
        }
        Boolean[][] memo = new Boolean[k + 1][sub + 1];
        boolean[] visited = new boolean[nums.length];
        return canPartition(nums, sub, k, sub, visited, memo);
    }

    private static boolean canPartition(int[] nums, int originalSub, int k, int sub,
                                        boolean[] visited, Boolean[][] memo) {
        if (k <= 0 || sub < 0) {
            return false;
        }
        if (sub == 0) {
            sub = originalSub;
            k = k - 1;
            if (k == 0) {
                return true;
            }
        }
        if (memo[k][sub] != null) {
            return memo[k][sub];
        }
        boolean found = false;
        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            found |= canPartition(nums, originalSub, k, sub - nums[i], visited, memo);
            visited[i] = false;
        }
        memo[k][sub] = found;
        return found;
    }

    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
        System.out.println(prob.canPartitionKSubsets(new int[]{5, 3, 2, 3, 4, 2, 2}, 4)); // false
        System.out.println(prob.canPartitionKSubsets(new int[]{1, 2, 3, 4}, 3)); // false
        System.out.println(prob.canPartitionKSubsets(new int[]{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, 5)); // true
        System.out.println(prob.canPartitionKSubsets(new int[]{5, 7, 3}, 3)); // false
        System.out.println(prob.canPartitionKSubsets(new int[]{2, 2, 10, 5, 2, 7, 2, 2, 13}, 3)); // true
    }
}

@@ -376,64 +376,8 @@
   %7D%0A
-        Boolean%5B%5D%5B%5D memo = new Boolean%5Bk + 1%5D%5Bsub + 1%5D;%0A
     
@@ -464,16 +464,19 @@
 ms, sub,
+ 0,
  k, sub,
@@ -479,30 +479,24 @@
 sub, visited
-, memo
 );%0A    %7D%0A%0A  
@@ -561,16 +561,25 @@
 inalSub,
+ int idx,
  int k, 
@@ -648,26 +648,8 @@
 ited
-, Boolean%5B%5D%5B%5D memo
 ) %7B%0A
@@ -666,21 +666,10 @@
  (k 
-%3C= 0 %7C%7C sub %3C
+==
  0) 
@@ -681,36 +681,35 @@
          return 
-fals
+tru
 e;%0A        %7D%0A   
@@ -745,238 +745,89 @@
     
-sub = originalSub;%0A            k = k - 1;%0A            if (k == 0) %7B%0A                return true;%0A            %7D%0A        %7D%0A        if (memo%5Bk%5D%5Bsub%5D != null) %7B%0A            return memo%5Bk%5D%5Bsub%5D;%0A        %7D%0A        boolean found = false;
+return canPartition(nums, originalSub, 0, k - 1, originalSub, visited);%0A        %7D
 %0A   
@@ -836,33 +836,35 @@
    for (int i = 
-0
+idx
 ; i %3C nums.lengt
@@ -990,17 +990,12 @@
     
-found %7C= 
+if (
 canP
@@ -1021,16 +1021,23 @@
 inalSub,
+ i + 1,
  k, sub 
@@ -1058,501 +1058,87 @@
 ited
-, memo);%0A            visited%5Bi%5D = false;%0A        %7D%0A        memo%5Bk%5D%5Bsub%5D = found;%0A
+)) %7B%0A         
        
- 
 return 
-found;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem698 prob = new Problem698();%0A        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B4, 3, 2, 3, 5, 2, 1%7D, 4)); // true%0A        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B5, 3, 2, 3, 4, 2, 1%7D, 4)); // true%0A        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B5, 3, 2, 3, 4, 2, 2%7D, 4)); //
+true;%0A            %7D%0A            visited%5Bi%5D =
  false
+;
 %0A   
@@ -1146,389 +1146,31 @@
     
-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        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B5, 7, 3%7D, 3)); // false%0A        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B2, 2, 10, 5, 2, 7, 2, 2, 13%7D, 3)); // true
+%7D%0A        return false;
 %0A   

Update problem 698