目标和

494. 目标和

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-‘ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-‘ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

解题思路

方法一：

动态规划

把数组的和表示为sum，假定left，right为某个子集的和，那么一定有 left - right = target，且left + right = sum

那么我们只要求出left组合有多少种方法，就能知道有多少种方法可以达到target

由left -（sum - left）= target ，可以推出 left = (target + sum) / 2

那么就能转化成01背包问题，装满容量为left的背包，有几种方法

1.确定dp数组及下标的含义

dp[j] 表示装满 j 容量的背包有多少种方法

2.确定递推公式

此题为01背包的组合问题

根据01背包的通式，若不考虑nums[i], 装满容量 j - nums[i]背包，有dp[ j - nums[i] ]种方法，

如果把num[i]装入正好装满容量为j的背包，凑成dp[j]就有dp[ j - nums[i] ]种方法

故递推公式为**dp[j] += dp[j-nums[i]]**，表示加入了物品nums[i]之后dp[j]新增了多少种方法，即装满容量 j 新增的方法

3.初始化dp数组

dp[0] = 1，背包容量为0有一种方法，表示什么都不放，该值必须初始化为1，否则无法递推下去

4.确定遍历顺序

先遍历物品，再遍历背包，01背包问题背包容量从大到小遍历

举例

输入：nums = {1,1,1,1,1} ，target = 3

bagsize = (target+sum)/2 = 4

dp数组的状态如图

代码

class Solution {
    //01背包问题
    //把数组分成两个堆left和right，left-right = traget, 即left-(sum-left)= target --> left = (sum + target)/2
    //问题变为在nuns集合中有多少中和为left的组合
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        if(Math.abs(target) > sum) return 0; //没有方法
        if((sum + target) % 2 == 1) return 0; //没有方法
        int bagsize = (sum + target)/2;
        //统计数组有多少种组合总和为bagsize 
        int[] dp = new int[bagsize+1];  //dp[j]表示装满j容量的背包，有几种方法
        dp[0] = 1;//背包容量为0有一种方法,表示什么都不放,如果为0则无法进行递归
        for(int i = 0; i < nums.length; i++){//遍历物品
            for(int j = bagsize; j >= nums[i]; j--){ //遍历背包
                //不考虑nums[i], 装满容量j-nums[i]背包，有dp[j-nums[i]]种方法
                dp[j] += dp[j-nums[i]]; //速推公式，表示加入了物品nums[i]之后背包容量为j新增的方法
            }
        }
        return dp[bagsize];

    }
}

• 时间复杂度：$O(n × m)$，n为数组nums大小，m为背包容量

• 空间复杂度：$O(m)$，m为背包容量

方法二：

回溯

把数组的和表示为sum，假定left，right为某个子集的和，那么一定有 left - right = target，且left + right = sum

由left -（sum - left）= target ，可以推出 left = (target + sum) / 2

那么我们只要求出数组中组合总和为left的子集个数即可

代码

class Solution {
    int count = 0; //统计组合总和数量
    List<Integer> path = new ArrayList<>();

    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for(int i = 0 ; i<nums.length; i++){
            sum += nums[i];
        }
        if(target>sum) return 0; //没有方法
        if((target+sum)%2!=0) return 0; //没有方法
        int left = (target+sum)/2;
        Arrays.sort(nums);
        backtrack(nums, left, 0, 0); //统计组合总和为left子集数量
        return count;

    }
    
	//回溯求组合总和，每个元素不可重复取
    public void backtrack(int[] nums, int target, int sum, int index) {
        if (sum == target) {
             count++;
        }
        for(int i = index; i < nums.length; i++){
            if(sum + nums[i]>target) continue;
            sum += nums[i];
            backtrack(nums, target, sum, i+1);
            sum -= nums[i];
        }
    }
}

时间复杂度：$O(n\times C_n^k)$，总共有$C_n^k$组合，每种组合需要$O(k)$的时间复杂度。另一方面，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度$O(n\times2^n)$

空间复杂度： $O(n)$，递归深度为n

方法三：

回溯

数组 nums的每个元素都可以添加符号 + 或 -，因此每个元素有 2 种添加符号的方法，n 个数共有 $2^n$ 种添加符号的方法，对应 $2^n$种不同的表达式。当 n个元素都添加符号之后，即得到一种表达式，如果表达式的结果等于目标数 target，则该表达式即为符合要求的表达式。

代码

class Solution {
    int count = 0;

    public int findTargetSumWays(int[] nums, int target) {
        backtrack(nums, target, 0, 0);
        return count;
    }

    public void backtrack(int[] nums, int target, int index, int sum) {
        if (index == nums.length) {
            if (sum == target) {
                count++;
            }
        } else {
            backtrack(nums, target, index + 1, sum + nums[index]);
            backtrack(nums, target, index + 1, sum - nums[index]);
        }
    }
}

时间复杂度：$O(2^n)$，其中 n 是数组的长度。回溯需要遍历所有不同的表达式，共有 $2^n$种不同的表达式

空间复杂度：$O(n)$