Leetcode 目标和（递归）

给你一个整数数组 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,0], target = 1
输出：2
解释：+0和-0算两种

---

【思路】：
因为存在大量子问题，所以递归实现。

【代码】：

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

function dfs(k, nums, target){
    if(k == nums.length - 1){
        if(nums[k] == target || nums[k] == -target) {
            if(nums[k] == 0)    return 2;       //+0 和 -0算两种
            else    return 1;
        }
        else    return 0;
    }
    return dfs(k + 1, nums, target - nums[k]) + dfs(k + 1, nums, target + nums[k]);
}

var findTargetSumWays = function(nums, target) {
    return dfs(0, nums, target);
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20