package leetcode;

/**
 * https://leetcode.com/problems/continuous-subarray-sum/
 */
public class Problem523 {
    public boolean checkSubarraySum(int[] nums, int k) {
        Boolean[][] memo = new Boolean[nums.length + 1][nums.length + 1];
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        return checkSubarraySum(nums, k, 0, nums.length, sum, memo);
    }

    private static boolean checkSubarraySum(int[] nums, int k, int i, int j, int sum, Boolean[][] memo) {
        if (i >= j) {
            return false;
        }
        if (j - i == 1) {
            return false;
        }
        if (sum == 0 && k == 0) {
            return true;
        }
        if (k == 0) {
            return false;
        }
        if (sum % k == 0) {
            return true;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        int vali = (i >= 0 && i < nums.length) ? nums[i] : 0;
        int valj = (j >= 0 && j < nums.length) ? nums[j] : 0;
        boolean a = checkSubarraySum(nums, k, i + 1, j, sum - vali, memo);
        boolean b = checkSubarraySum(nums, k, i, j - 1, sum - valj, memo);
        boolean c = checkSubarraySum(nums, k, i + 1, j - 1, sum - vali - valj, memo);
        boolean result = a | b | c;
        memo[i][j] = result;
        return result;
    }

    public static void main(String[] args) {
        Problem523 prob = new Problem523();
        System.out.println(prob.checkSubarraySum(new int[]{23, 2, 4, 6, 7}, 6)); // true
        System.out.println(prob.checkSubarraySum(new int[]{23, 2, 6, 4, 7}, 6)); // true
        System.out.println(prob.checkSubarraySum(new int[]{23, 2, 6, 4, 8}, 6)); // true
        System.out.println(prob.checkSubarraySum(new int[]{1, 2, 3}, 4)); // false
        System.out.println(prob.checkSubarraySum(new int[]{23, 2, 6, 4, 7}, 0)); // false
        System.out.println(prob.checkSubarraySum(new int[]{0, 0}, 0)); // true
        System.out.println(prob.checkSubarraySum(new int[]{0}, 0)); // false
    }
}

@@ -165,82 +165,8 @@
 ) %7B%0A
-        Boolean%5B%5D%5B%5D memo = new Boolean%5Bnums.length + 1%5D%5Bnums.length + 1%5D;%0A
     
@@ -259,200 +259,117 @@
     
-return checkSubarraySum(nums, k, 0, nums.length, sum, memo);
+if (nums.length == 1) %7B
 %0A    
-%7D%0A%0A
     
-private static boolean checkSubarraySum(int%5B%5D nums, int k, int i, int j, int sum, Boolean%5B%5D%5B%5D memo) %7B%0A        if (i %3E= j
+    return false;%0A        %7D%0A        if (sum == 0 && k == 0 && nums.length %3E 1
 ) %7B%0A
@@ -379,36 +379,35 @@
          return 
-fals
+tru
 e;%0A        %7D%0A   
@@ -415,22 +415,45 @@
     
-if (j - i == 1
+for (int i = nums.length; i %3E= 0; i--
 ) %7B%0A
@@ -460,37 +460,46 @@
             
-return false;
+if (i %3C nums.length) %7B
 %0A        %7D%0A 
@@ -491,34 +491,32 @@
 ) %7B%0A        
-%7D%0A
         
 if (sum == 0
@@ -507,57 +507,63 @@
     
-if (
 sum 
-== 0 && k == 0) %7B%0A            return true
+-= nums%5Bi%5D;%0A            %7D%0A            int tmp = sum
 ;%0A  
@@ -571,58 +571,42 @@
     
- %7D%0A
      
-   if (k
+for (int j
  =
-=
  0
-) %7B%0A            return false;
+; j %3C i; j++) %7B
 %0A   
@@ -602,34 +602,32 @@
  j++) %7B%0A        
-%7D%0A
         if (sum 
@@ -626,17 +626,11 @@
 if (
-sum %25 
 k 
-=
+!
 = 0)
@@ -648,65 +648,59 @@
     
-return true;%0A        %7D%0A        if (memo%5Bi%5D%5Bj%5D != null) %7B%0A
+        if (tmp %25 k == 0 && i - j %3E 1) %7B%0A          
     
@@ -711,25 +711,21 @@
     
+  
 return 
-memo%5Bi%5D%5Bj%5D
+true
 ;%0A  
@@ -730,26 +730,24 @@
         
-%7D%0A
         
 int vali
@@ -742,424 +742,182 @@
     
-int vali = (i %3E= 0 && i %3C nums.length) ? nums%5Bi%5D : 0;%0A        int valj = (j %3E= 0 && j %3C nums.length) ? nums%5Bj%5D : 0;%0A        boolean a = checkSubarraySum(nums, k, i + 1, j, sum - vali, memo);%0A        boolean b = checkSubarraySum(nums, k, i, j - 1, sum - valj, memo);%0A        boolean c = checkSubarraySum(nums, k, i + 1, j - 1, sum - vali - valj, memo);%0A        boolean result = a %7C b %7C c;%0A        memo%5Bi%5D%5Bj%5D = result;
+    %7D%0A                %7D else if (k == 0 && tmp == 0 && i - j %3E 1) %7B%0A                    return true;%0A                %7D%0A                tmp -= nums%5Bj%5D;%0A            %7D%0A        %7D
 %0A   
@@ -932,14 +932,13 @@
 urn 
-result
+false
 ;%0A  
@@ -1623,20 +1623,350 @@
 ); // false%0A
+        System.out.println(prob.checkSubarraySum(new int%5B%5D%7B23, 2, 4, 6, 7%7D, -6)); // true%0A        System.out.println(prob.checkSubarraySum(new int%5B%5D%7B0%7D, -1)); // false%0A        System.out.println(prob.checkSubarraySum(new int%5B%5D%7B0, 0, 1%7D, 0)); // true%0A        System.out.println(prob.checkSubarraySum(new int%5B%5D%7B0, 2%7D, 0)); // false%0A
     %7D%0A%7D%0A

Update problem 523