Leetcode-494题解

leetcode 494 题解
DFS。

复习一下DFS。

题目

给你一个非负整数数组 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

思路

一开始想用vector数组表示所有可能的结果，但是超时了；尝试使用int数组+二分法，分别计算前后部分，但是需要分别处理数组中含有奇数个或者偶数个数的情况，相对麻烦，最后还是使用了DFS来解。DFS思路非常清晰，当数组中的所有数都被加入到表达式当中时，判断是否等于target，若相等，则sum加1，然后返回。当数组还有数没有加入到表达式当中时，分别考虑这个数为正数（+）和为负数（-）的情况。

注意

记得考虑第一个数为负数时的情况。

改进

使用动态规划。

示例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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