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

解题思路：回溯

​ 这道题我们在背包问题专题就遇到过，其实用回溯来解决这道题是更简单的，不像动态规划那么复杂，但是缺点就是时间复杂度肯定要高得多，这没办法！不过我们是回溯专题，所以就用回溯来求解这道题！

​ 其实这道题用回溯并不难，就是一个暴力搜索，因为对于一个 nums 数组，每个元素我们可以看作两个选择：nums[i] 和 -nums[i]。然后我们只要递归遍历这两种选择对于所有元素的所有路径，最后判断符合要求的就累加次数即可！

​ 下面是算法步骤：

1. 函数头的设计：

   • 首先我们需要一个全局变量 ret，来存放结果集，至于为什么作为全局变量，前面强调很多次了，就是简化函数头的参数。

   • 然后因为我们需要知道当前遍历到哪个元素了，所以需要一个局部 index 变量来标识下标！

   • 最后还需要一个局部变量 path，存放当前路径的运算结果！这道题其实将 path 设为全局变量的话，我们就要写冗余的代码，并且会超时，所以这里干脆将其作为函数参数进行传递即可！

     void dfs(vector<int>& nums, int target, int index, int path);

2. 函数体的内容：

   • 函数体很简单，就是递归正负数两种情况：

     dfs(nums, target, index + 1, path + nums[index]); // 正数处理
     dfs(nums, target, index + 1, path - nums[index]); // 负数处理

3. 递归函数出口：

   • 当下标遍历超出数组范围了，则此时判断一下此时运算结果是否符合要求，然后进行返回即可：

     // 递归函数出口
     if(index == nums.size())
     {
         if(path == target)
             ret++;
         return;
     }

​ 完整代码如下所示：

class Solution {
    int ret;  // 存放结果集
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        dfs(nums, target, 0, 0);
        return ret;
    }
 
    void dfs(vector<int>& nums, int target, int index, int path)
    {
        // 递归函数出口
        if(index == nums.size())
        {
            if(path == target)
                ret++;
            return;
        }
 
        dfs(nums, target, index + 1, path + nums[index]); // 正数处理
        dfs(nums, target, index + 1, path - nums[index]); // 负数处理
    }
};