LeetCode494-目标和

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/target-sum/

中文链接：https://leetcode-cn.com/problems/target-sum/

题目详述

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

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

示例 1:

1
2
3
4
5
6
7
8
9
10
11
输入: 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。

注意:

  1. 数组的长度不会超过20，并且数组中的值全为正数。
  2. 初始的数组的和不会超过1000。
  3. 保证返回的最终结果为32位整数。

题目详解

方法一：DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode_00494 {

    public int findTargetSumWays(int[] nums, int S) {
        return findTargetSumWays(nums, 0, 0, S);
    }

    private int findTargetSumWays(int[] nums, int i, int sum, int S) {
        if (i == nums.length) {
            return sum == S ? 1 : 0;
        }
        return findTargetSumWays(nums, i + 1, sum + nums[i], S) + findTargetSumWays(nums, i + 1, sum - nums[i], S);
    }
}

上面的递归调用存在很多重复的子过程，我们可以利用缓存把子过程的结果保存下来。

方法二：记忆化搜索。

  • 因为初始的数组的和不会超过 1000，所以数据的可能范围为 [-1000, 1000]。
  • 运用缓存数组需要加上偏移量 1000 来保证下标非负。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeetCode_00494 {

    public int findTargetSumWays(int[] nums, int S) {
        int[][] cache = new int[nums.length][2001];
        for (int[] row : cache) {
            // 运用 -1 表示不存在
            Arrays.fill(row, -1);
        }
        return findTargetSumWays(nums, 0, 0, S, cache);
    }

    private int findTargetSumWays(int[] nums, int i, int sum, int S, int[][] cache) {
        if (i == nums.length) {
            return sum == S ? 1 : 0;
        }
        // 加上偏移量 1000 保证下标非负
        if (cache[i][1000 + sum] == -1) {
            cache[i][1000 + sum] = findTargetSumWays(nums, i + 1, sum + nums[i], S, cache) + findTargetSumWays(nums, i + 1, sum - nums[i], S, cache);
        }
        return cache[i][1000 + sum];
    }
}

方法三：动态规划。

  • 本问题可以转化为 Subset Sum 问题。
  • Subset Sum 问题可以运用 01背包 来解决。

可以将数组分为两部分，P 和 N，其中 P 使用正号，N 使用负号，推导过程如下：

1
2
3
4
sum(P) - sum(N) = target
sum(P) + sum(N) = sum(nums)
2 * sum(P) = target + sum(nums)
sum(P) = (target + sum(nums)) / 2

因此问题就转化为了 Subset Sum 问题：在给定的集合中找到子集元素加和等于 (target + sum(nums)) / 2 的方法总数。

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
public class LeetCode_00494 {

    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 所有元素加和都达不到目标值或 (S + sum) 为奇数显然不满足条件
        if (sum < S || ((S + sum) & 1) == 1) {
            return 0;
        }
        return subsetSum(nums, (S + sum) >> 1);
    }

    /**
     * 传入一个数组和目标值，返回数组所表示的集合的子集中元素的加和等于目标值的方法总数。
     * 这是一个 01背包 问题（每个元素有选与不选两种选择）。
     * @param nums 数组
     * @param s 目标值
     * @return 子集中元素的加和等于目标值的情况总数
     */
    private int subsetSum(int[] nums, int s) {
        int[] dp = new int[s + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = s; i >= num; --i) {
                dp[i] += dp[i - num];
            }
        }
        return dp[s];
    }
}

实际上，LeetCode416-分割等和子集 也是一个Subset Sum 问题。只不过它不需要求方法总数，只需要判断存在性。