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, k, sub, visited, memo);
    }

    private static boolean canPartition(int[] nums, int k, int sub, boolean[] visited, Boolean[][] memo) {
        if (sub == 0 && k == 0) {
            return true;
        }
        if (k <= 0 || sub <= 0) {
            return false;
        }
        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, k - 1, 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
    }
}

@@ -515,16 +515,21 @@
 on(nums,
+ sub,
  k, sub,
@@ -612,19 +612,76 @@
 int 
-k, int sub,
+originalSub, int k, int sub,%0A                                       
  boo
@@ -732,24 +732,23 @@
 if (
-sub == 0 && k ==
+k %3C= 0 %7C%7C sub %3C
  0) 
@@ -768,19 +768,20 @@
  return 
-tru
+fals
 e;%0A     
@@ -797,31 +797,101 @@
     if (
-k %3C= 0 %7C%7C sub %3C
+sub == 0) %7B%0A            sub = originalSub;%0A            k = k - 1;%0A            if (k =
 = 0) %7B%0A 
@@ -897,37 +897,54 @@
             
+  
+  
 return 
-false;
+true;%0A            %7D
 %0A        %7D%0A 
@@ -1241,21 +1241,30 @@
 n(nums, 
-k - 1
+originalSub, k
 , sub - 
@@ -1478,18 +1478,16 @@
 m698();%0A
-//
         
@@ -1568,34 +1568,32 @@
 %7D, 4)); // true%0A
-//
         System.o
@@ -1666,34 +1666,32 @@
 %7D, 4)); // true%0A
-//
         System.o
@@ -1773,18 +1773,16 @@
 / false%0A
-//
         
@@ -1970,18 +1970,16 @@
 // true%0A
-//
         
@@ -2053,20 +2053,126 @@
 ); // false%0A
+        System.out.println(prob.canPartitionKSubsets(new int%5B%5D%7B2, 2, 10, 5, 2, 7, 2, 2, 13%7D, 3)); // true%0A
     %7D%0A%7D%0A

Update problem 698