1
class Solution {
2
  public boolean canPartition(int[] nums) {
3
    int sum = 0;
4
    for (int i = 0; i < nums.length; i++) {
5
      sum = sum + nums[i];
6
    }
7

8
    if (sum % 2 != 0) {
9
      return false;
10
    }
11
    int[][] dp = new int[nums.length + 1][sum];
12
    for (int i = 0; i < dp.length; i++) {
13
      Arrays.fill(dp[i], -1);
14
    }
15

16
    return helper(nums, sum / 2, 0, dp) >= 1 ? true : false;
17
  }
18

19
  public int helper(int[] nums, int sum, int i, int[][] dp) {
20
    if (i == nums.length && sum == 0) {
21
      return 1;
22
    }
23
    if (i == nums.length) {
24
      return 0;
25
    }
26
    if (sum < 0) {
27
      return 0;
28
    }
29
    if (dp[i][sum] != -1) {
30
      return dp[i][sum];
31
    }
32
    if (sum < nums[i]) {
33
      return dp[i][sum] = helper(nums, sum, i + 1, dp);
34
    }
35
    int a = helper(nums, sum - nums[i], i + 1, dp); // Take the value
36
    int b = helper(nums, sum, i + 1, dp); // Not take the value
37
    if (a == 1
38
        || b == 1) { // if any of the options is returning true then whole answer would be true
39
      return dp[i][sum] = 1;
40
    } else {
41
      return dp[i][sum] = 0;
42
    }
43
  }
44
}