目标和

题目

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

提示：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

题解

方法一：

思路

n个数的数组，每个数有两种符号，组合方式最多有2^n种。

每个数的二进制位有0或1两种取值，分别代表减号和加号。

遍历0到2^n-1，假设当前遍历到i，i的二进制位数与nums中元素个数是一致的。通过遍历i的二进制位确定nums数组中元素累积运算的符号是加还是减。再判断累积运算后的元素和是否位target确定当前这种符号分配方式是否可取。

由于每次都要遍历n个二进制位。时间复杂度为O(n * 2^n), n最多也就20.运算次数高达20* 1024* 1024=20,971,520, 超时！

在这n个二进制位的加减法中有很多是重复计算的若能将前面部分累计运算结果存储起来之后再用可以减少时间复杂度。

回溯法就是一个很好的方法。回溯法是一个递归算法。递归的每一层都保留了前面层的运算和。时间复杂度降低为O(2^n)。本题中从千万数量级变为百万数量级，能过。

代码

class Solution {
public:
    int cnt;
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums, 0, 0, target);
        return cnt;
    }
    void dfs(vector<int>& nums, int cur, int lev, int target) {
        if (lev == nums.size()) {
            if (cur == target) cnt++;
            return ;
        } 
        dfs(nums, cur+nums[lev], lev+1, target);
        dfs(nums, cur-nums[lev], lev+1, target);
    }
};

方法二

思路

可以通过某种转变将问题转换为类似01背包问题。

sum为nums的和，pos为nums中带正号的和，neg为nums中带负号的和。

pos+neg=sum，pos-neg=target，所以sum-2* neg = target。

neg = (sum-target)/2。neg为整数，sum-target必然为偶数。

dp[i][j] 为前i个数中选取若干数之和为j的方式数量。

dp[i][j] = dp[i][j-1]

dp[i][j] = dp[i][j]+dp[i][j-nums[i]] , j >= nums[i]

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int s = 0;
        for (auto num:nums) s += num;
        if (s < target || (s - target)%2) return 0;
        vector<int> dp((s - target)/2+1, 0);
        dp[0] = 1;
        for (int i=0; i<nums.size(); i++) {
            for (int j=dp.size()-1; j>=0; j--) {
                if (j >= nums[i]) dp[j] += dp[j-nums[i]];
            }
        }
        return dp.back();
    }
};