494. Target Sum

,

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 0, 0, target);
    }

    private int dfs(int[] nums, int i, int sum, int target) {
        if (i == nums.length) {
            if (sum == target) {
                return 1;
            } else {
                return 0;
            }
        } else {
            return dfs(nums, i + 1, sum + nums[i], target) + dfs(nums, i + 1, sum - nums[i], target);
        }
    }
}

DP

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
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 设从 nums 中选择了 a 个数字作为正数，选择了 b 个数字作为负数，可知：
        // sum(a) + sum(b) = sum(nums)
        // sum(a) - sum(b) = target
        // 可推导出 sum(a) = (sum(nums) + target) / 2
        // 即将问题转换为从 nums 中选择一部分数字，其和为 (sum(nums) + target) / 2 的方案数

        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        int tmpSum = sum + target;
        if (tmpSum < 0 || (tmpSum & 1) == 1) {
            return 0;
        }

        int targetSum = tmpSum >>> 1;

        // 定义 dp[i][j] 为从 nums 前 i 个数字中选择部分数字组成和 j 的方案数
        int[][] dp = new int[nums.length + 1][targetSum + 1];
        dp[0][0] = 1; // 选择 0 个数字只能组成和 0

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j <= targetSum; j++) {
                // 选择 nums[i - 1]
                if (j - nums[i - 1] >= 0) {
                    dp[i][j] = dp[i - 1][j - nums[i - 1]];
                }

                // 不选择 nums[i - 1]
                dp[i][j] += dp[i - 1][j]; // 注意此处是 += 而不是 |=
            }
        }

        return dp[nums.length][targetSum];
    }
}

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        int doubleTargetSum = sum + target;
        if (doubleTargetSum < 0 || (doubleTargetSum & 1) == 1) {
            return 0;
        }

        int targetSum = doubleTargetSum >> 1;

        int[] dp = new int[targetSum + 1];
        dp[0] = 1;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = targetSum; j >= 0; j--) {
                if (j - nums[i - 1] >= 0) {
                    dp[j] = dp[j - nums[i - 1]] + dp[j];
                }
            }
        }

        return dp[targetSum];
    }
}

References

494. Target Sum
剑指 Offer II 102. 加减的目标值