题解 | #目标和#

题目的主要信息：

给定一个整数数组nums和一个整数target，请你返回该数组能构成多少种不同的表达式等于target。

规则如下：

1. 将数组里每个整数前面可以添加"+"或者"-"符号，组成一个表达式，例如[1,2]，可以变成”+1+2","+1-2","-1+2","-1-2"，这四种
2. 只能添加"+"与"-"符号，不能添加其他的符号
3. 如果构不成等于target的表达式，请返回0
4. 保证返回的结果个数在整数范围内

方法一：

暴力递归。用count记录所有目标和表达式的个数，用dfs进行递归遍历所有可能的表达式。dfs的结束条件是遍历到了数组的末尾且表达式之和为target，否则分两种情况继续进行递归遍历，分别是添加+号和添加-号。

具体做法：

class Solution {
public:
    int count=0;
    void dfs(vector<int> nums, int target, int i, int sum) {
        if (i == nums.size() && sum == target) {//如果遍历到数组的末尾且和为目标和，则表示找到一个表达式
            count ++;
            return;
        }
        if (i == nums.size()) {//如果遍历到了数组的末尾且不为目标和，则该表达式行不通
            return;
        }
        dfs(nums, target, i + 1, sum + nums[i]);//添加+号
        dfs(nums, target, i + 1, sum - nums[i]);//添加-号
    }
    int findTargetSumWays(vector<int>& nums, int target) {
        if (nums.size() == 0){//如果数组大小为0 返回0
            return 0;
        }
        dfs(nums, target, 0, 0);//递归遍历所有可能的情况
        return count;
    }
};

复杂度分析：

• 时间复杂度：$O(2^n)O(2^n)$，需要递归遍历所有可能的表达式，数组长度为n，则可能的表达式有$2^{n}2^n$种。
• 空间复杂度：$O(n)O(n)$，递归栈的大小为n。

方法二：

动态规划。设数组和为sum，首先我们把数组元素按照符号分为两组，前面加号的分为一组，和为a；前面减号的分为一组，和为b。根据这个分组，可以得到两个式子：

• a+b=sum
• a−b=target

得到：a=(sum+target)/2。 因此问题就转换为，求和为a的子数组个数，采用动态规划的方法来做。动态数组dp[i]的含义为和为i的子数组有多dp[i]个。遍历一遍数组元素，自顶向下更新动态数组，最后返回dp[a]。 具体做法：

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        if(nums.size()==0) {//如果数组大小为0，返回0
            return 0;
        }
        int sum = 0;
        for(int i = 0;i < nums.size();i++){//先计算数组之和
            sum += nums[i];
        }
        if((sum + target) % 2) {//如果sum+target不是偶数，返回0
            return 0;
        }
        int a = (sum+target)/2;//a为添加加号的数字
        vector<int> dp(a+1);
        dp[0] = 1;//初始化动态数组
        for(int i = 0;i < nums.size();i++){//遍历一遍所有元素
            for(int j = a;j >= nums[i];j--){//自顶向下更新动态数组
                dp[j] += dp[j-nums[i]];
            }
        }
        return dp[a];
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，双重for循环。
• 空间复杂度：$O(n)O(n)$，动态数组大小为$O(n)O(n)$。