494. 目标和

leetcode 494. 目标和

题目：494. 目标和

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例:

输入：nums: [1, 1, 1, 1, 1], S: 3
输出: 5
解释：
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
一共有5种方法让最终目标和为3。

提示:

• 数组非空，且长度不会超过 20 。
• 初始的数组的和不会超过 1000 。
• 保证返回的最终结果能被 32 位整数存下。

方法一：动态规划

思路：动态规划。状态转移方程为：dp[j] = dp[j] + dp[j - nums[i]]。dp[j]表示装满空间j有多少中方案。根据提意，可以把数组划分为两部分，一部分minuend为被减数（即前面加符号 + 的部分），一部分subtractive为减数（即前面加负号的部分），当sum(minuend) - sum(subtractive) = S，即为一种方案数，将该等式左右两边同时加上sum(minuend)、sum(subtractive)，得到sum(minuend) - sum(subtractive) + sum(minuend) + sum(subtractive) = S + sum(minuend) + sum(subtractive)，又sum(nums) = sum(minuend) + sum(subtractive),化简可得sum(minuend) = (S + sum(nums)) / 2。由上述等式可得，我们只需从nums挑选几个元素使得它们的和刚好等于sum(minuend)，即为一种方案数。从而将问题转换为01背包的变种问题，即从n个元素的数组中，挑选出几个元素使得刚好装满空间为sum(minuend)的背包的方案数。

运行数据：执行用时：3 ms，内存消耗：36.6 MB

复杂度分析：

• 时间复杂度：O(n * target)，n为nums的长度，target = (sum + S) / 2，sum为nums的所有元素之和。
• 空间复杂度：O(target)，target = (sum + S) / 2，sum为nums的所有元素之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// LeetCode指定调用方法 
public int findTargetSumWays(int[] nums, int S) {
		
    int sum = 0;
    for (int i : nums) {
        sum += i;
    }

    if (sum < S || ((sum + S) & 1) == 1) {
        return 0;
    }

    int target = (sum + S) / 2;
    int[] dp = new int[target + 1];
    dp[0] = 1;
    for (int i = 0; i < nums.length; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] + dp[j - nums[i]];
        }
    }

    return dp[target];
}

方法二：DFS（深度优先搜索）

思路：DFS（深度优先搜索）。数组中每个元素都可以分别使用+和-去计算，如果最后等于S就计入1次。

运行数据：执行用时：645 ms，内存消耗：36.7 MB

复杂度分析：

• 时间复杂度：O(2^n)，递归深度为n。
• 空间复杂度：O(n)，递归深度为n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

// LeetCode指定调用方法 
public int findTargetSumWays(int[] nums, int S) {
		
    return dfs(nums, S, 0);
}

// DFS(深度优先搜索)
private int dfs(int[] nums, int S, int t) {

    if (t == nums.length) {
        return S == 0 ? 1 : 0;
    }

    return dfs(nums, S - nums[t], t + 1) + dfs(nums, S + nums[t], t + 1);
}

学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。

才疏学浅，若有错误或不当之处，可批评指正，还请见谅！