566，DFS解目标和问题

Original 博哥数据结构和算法 2022-05-01

We went through a lot, but we stayed together.

我们经历了各种风风雨雨，但依然团结一心。

问题描述

来源：LeetCode第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<=100

DFS解决

这题让在数组中每个元素前面添加'+'或'-'，组成算术表达式并且他的和等于target，问有多少种方式。每个元素只能有两种选择，要么添加'+'要么添加'-'，所以我们很容易想到的是二叉树。假如使用数组[1,1,1,1]中的所有元素通过'+'或'-'符号构成2，如下图所示

我们让每个节点的左子节点选择'-'，右子节点选择'+'，计算从根节点到叶子节点所有元素的和是否等于target，如果等于，说明找到了一个满足条件的表达式，只需要计算所有满足条件的个数即可，来看下代码

 1//不同表达式的数目
 2int count = 0;
 3
 4public int findTargetSumWays(int[] nums, int target) {
 5    dfs(nums, target, 0, 0);
 6    return count;
 7}
 8
 9//从根节点开始往下累加，到叶子节点的时候如果累加值等于target，
10//说明找到了一条符合条件的表达式
11private void dfs(int[] nums, int target, int sum, int index) {
12    //判断从根节点到当前叶子节点这条路径是否走完了
13    if (index == nums.length) {
14        //如果当前累加值等于target，说明找到了一条符号条件的表达式
15        if (target == sum)
16            count++;
17        return;
18    }
19    //左子树数负数，要减去
20    dfs(nums, target, sum - nums[index], index + 1);
21    //右子树是正数，要加上
22    dfs(nums, target, sum + nums[index], index + 1);
23}

这题我们还可以修改一下，上面计算的时候是从根节点到叶子节点的累加，其实我们还可以从根节点到叶子节点往下减，根节点默认值是target，到叶子节点计算完的时候如果值为0，说明找到了一个满足条件的表达式，原理都差不多，来看下代码

 1//不同表达式的数目
 2int count = 0;
 3
 4public int findTargetSumWays(int[] nums, int target) {
 5    dfs(nums, target, 0);
 6    return count;
 7}
 8
 9//从更节点开始往下减
10private void dfs(int[] nums, int target, int index) {
11    //判断当前路径是否走完了
12    if (index == nums.length) {
13        //如果走完了，减到最后等于0，说明找到了一条符号条件的表达式
14        if (target == 0)
15            count++;
16        return;
17    }
18    dfs(nums, target - nums[index], index + 1);
19    dfs(nums, target + nums[index], index + 1);
20}

或者还可以这样写，直接通过dfs返回

 1public int findTargetSumWays(int[] nums, int target) {
 2    return dfs(nums, target, 0);
 3}
 4
 5private int dfs(int[] nums, int target, int index) {
 6    if (index == nums.length) {
 7        return target == 0 ? 1 : 0;
 8    }
 9    int res = 0;
10    res += dfs(nums, target - nums[index], index + 1);
11    res += dfs(nums, target + nums[index], index + 1);
12    return res;
13}