1
class Solution {
2
  public int findTargetSumWays(int[] nums, int target) {
3
    // Solution 1
4
    int sum = 0;
5
    for (int x : nums) sum += x;
6
    if (((sum - target) % 2 == 1) || (target > sum)) return 0;
7

8
    int n = nums.length;
9
    int s2 = (sum - target) / 2;
10
    int[][] t = new int[n + 1][s2 + 1];
11
    t[0][0] = 1;
12

13
    for (int i = 1; i < n + 1; i++) {
14
      for (int j = 0; j < s2 + 1; j++) {
15
        if (nums[i - 1] <= j) t[i][j] = t[i - 1][j] + t[i - 1][j - nums[i - 1]];
16
        else t[i][j] = t[i - 1][j];
17
      }
18
    }
19
    return t[n][s2];
20

21
    // Solution 2
22
    //         int sum = 0;
23
    //         for(int x : nums)
24
    //             sum += x;
25
    //         if(((sum - target) % 2 != 0) || (target > sum))
26
    //             return 0;
27

28
    //         int n = nums.length;
29
    //         int s2 = (sum - target)/2;
30

31
    //         int[][] t = new int[n + 1][s2 + 1];
32
    //         for(int i = 0; i < n + 1; i++) {
33
    //             for(int j = 0; j < s2 + 1; j++) {
34
    //                 if(i == 0)
35
    //                     t[i][j] = 0;
36
    //                 if(j == 0)
37
    //                     t[i][j] = 1;
38
    //             }
39
    //         }
40

41
    //         for(int i = 1; i < n + 1; i++) {
42
    //             for(int j = 1; j < s2 + 1; j++) {
43
    //                 if((nums[i - 1] > j) || (nums[i - 1] == 0))
44
    //                     t[i][j] = t[i - 1][j];
45
    //                 else
46
    //                     t[i][j] = t[i - 1][j] + t[i - 1][j - nums[i - 1]];
47
    //             }
48
    //         }
49

50
    //         int count = 0;
51
    //         for(int x : nums)
52
    //             if(x == 0)
53
    //                 count++;
54

55
    //         return (int)(Math.pow(2,count)) * t[n][s2];
56
  }
57
}