Leetcode-Java/TargetSum.java at master · brentquackenbush/Leetcode-Java · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class TargetSum {

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 3;
        System.out.println(findTargetSumWays(nums, target));
    }

    //    public static int findTargetSumWays(int[] nums, int S) {
//        int sum = 0;
//        for (int i = 0; i < nums.length; i++) {
//            sum += nums[i];
//        }
//        if(S > sum || (sum + S) % 2 == 1)   return 0;
//        return subsetSum(nums, (sum + S) / 2);
//    }
//
//    private static int subsetSum(int[] nums, int S){
//        if(S < 0) return 0;
//        int[] dp = new int[S + 1];
//        dp[0] = 1;
//        for (int num: nums) {
//            for (int j = S; j >= num; j--) {
//                dp[j] += dp[j - num];
//            }
//        }
//        return dp[S];
//    }
    public static int findTargetSumWays(int[] nums, int s) {
        int sum = 0;

        for (int i : nums) sum += i;
        if (s > sum || s < -sum) return 0;

        int[] dp = new int[2 * sum + 1];
        dp[sum] = 1;

        for (int i = 0; i < nums.length; i++) {
            int[] next = new int[2 * sum + 1];
            for (int k = 0; k < 2 * sum + 1; k++) {
                if (dp[k] != 0) {
                    next[k + nums[i]] += dp[k];
                    next[k - nums[i]] += dp[k];
                }
            }
            dp = next;
        }
        return dp[sum + s];
    }

}