【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。

方法一：暴力法（回溯算法）

对于回溯法，需要重点考虑三个问题：

  • 路径：目前为止已经做出的选择（目前所产生的和sum）
  • 选择列表：当前可以做的选择（给nums[i]加号或者减号）
  • 结束条件：到达决策树的叶节点时，无法再继续做选择，结束。（用完了数组nums中的每一个数）
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
class Solution {
    private int[] nums;
    private int S;
    //res记录能组合成目标数S的方法数
    private int res;
    public int findTargetSumWays(int[] nums, int S) {
        this.nums = nums;
        this.S = S;
        if(nums.length == 0)
            return 0;
        backtrack(0, 0);
        return res;
    }

    //回溯主体
    public void backtrack(int i, int sum) {
        //结束条件：用完了数组中的所有元素
        if(i == nums.length){
            //如果使用完所有元素构成了目标数S，则res加1
            if(sum == S)
                res++;
            return;
        }
        //首先尝试给nums[i]加正号，做选择、递归下一步、撤销选择
        sum += nums[i];
        backtrack(i + 1, sum);
        sum -= nums[i];
        //再尝试给nums[i]加负号，做选择、递归下一步、撤销选择
        sum -= nums[i];
        backtrack(i + 1, sum);
        sum += nums[i];
    }
}

方法二：动态规划（01背包问题）

1.定义状态

定义dp[i][j]为给子数组nums[0…i]的每个元素加号或减号，能凑成目标数S的方法数

由于目标数可正可负，因此j也应该既有正也有负。在这里我们令j的取值为从-sum到+sum。其中sum为数组nums中所有元素之和。

2.Base Case

当i为0时，也就是说只用数组的第一个元素nums[0]去凑成目标数S，有多少种方法。分两种情况：

  • 当nums[0]为0时，要凑成0有两种方法（给nums[0]加正号或负号都可以），要凑成其他数就没有办法了。
  • 当nums[0]非0时，凑成nums[0]或-nums[0]有一种方法，要凑成其他数没有办法。

3.状态转移方程

对于数组中的每个数nums[i]，我们都有两种选择：

  • 给nums[i]加号+
  • 给nums[i]减号-

如果给nums[i]加号，那么$dp[i][j] = dp[ i - 1 ][ j - nums[i]]$,即：不算nums[i]这个数，前面的nums[0…i-1]要凑成S-nums[i]。这样算上nums[i]后才能凑成目标数S。

如果给nums[i]减号，那么$dp[i][j] = dp[ i - 1 ][ j + nums[i]]$,即：不算nums[i]这个数，前面的nums[0…i-1]要凑成S+nums[i]。这样算上nums[i]后才能凑成目标数S。

把这两种选择每种的方法数相加，就是dp[i][j]，即：$dp[ i ][ j ] = dp[ i - 1 ][ j - nums[ i ] ] + dp[ i - 1 ][ j + nums[ i ] ]$

代码

注意：在上述中：dp数组对于j的取值为从-sum到+sum，但具体到代码上时，由于数组的索引不可能为负，因此需要进行适当的调整，把j的取值改为从0到2*sum

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
public int findTargetSumWays(int[] nums, int S) {
    //处理边界情况
    if(nums == null || nums.length == 0)
        return 0;
    if(nums.length == 1)
        return (nums[0] == S || nums[0] == -S) ? 1 : 0;
    //sum记录数组中所有元素之和
    int sum = 0;
    for(int num: nums)
        sum += num;
    //如果S比数组中所有元素之和都大，那么肯定无法得到目标数S，返回0
    if (Math.abs(S) > Math.abs(sum)) 
        return 0;
    int[][] dp = new int[nums.length][2 * sum + 1];
    //设置base case
    if(nums[0] == 0)
        dp[0][sum] = 2;
    else{
        dp[0][sum + nums[0]] = 1;
        dp[0][sum - nums[0]] = 1;
    }
    //状态转移（填充dp数组）
    for(int i = 1; i < nums.length; i++){
        for(int j = -sum; j <= sum; j++){
            if(j + nums[i] > sum)
                dp[i][j + sum] = dp[i - 1][j + sum - nums[i]];
            else if(j - nums[i] < -sum)
                dp[i][j + sum] = dp[i - 1][j + sum + nums[i]];
            else
                dp[i][j + sum] = dp[i - 1][j + sum - nums[i]] + dp[i - 1][j + sum + nums[i]];
        }
    }
    return dp[nums.length - 1][S + sum];
}