目标和 | 徐年の博客

力扣 494. 目标和

题目说明

给你一个整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
- 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 100

示例

示例 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：

1 2	输入：nums = [1], target = 1 输出：1

笔者理解

此题是一道DFS算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题用深度优先比较直接了当，在进行减枝操作之后效率也还客观，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * DFS
     * 减枝优化策略
     */

    // 将结果和数集放在成员变量中，方便调用
    int result;
    int[] nums;
    int[] sum;

    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        result = 0;
        this.nums = nums;

        int[] sum = new int [n];
        sum[n - 1] = nums[n - 1];

        // 计算当前位置后的数的最大和
        for(int i = n - 2; i >= 0; i--) {
            sum[i] = sum[i + 1] + nums[i];
        }
        this.sum = sum;

        // 是否选择第一个数
        dfs(0, -nums[0], target);
        dfs(0, nums[0], target);

        return result;
    }

    public void dfs(int index, int count, int target) {
        // 所有数计算完了，判断是否等于目标值
        if (index == nums.length - 1) {
            if (count == target) {
                result++;
            }
            return;
        }

        // 如果当前可能加上后面所有数的最大值还是小于目标值
        // 或者
        // 当前可能减去后面所有数的最大值还是大于目标值
        // 那么当前可能就没有必要尝试了
        if (count + sum[index] < target || count - sum[index] > target) {
            return;
        }
        
        // 操作第index + 1个数
        dfs(index + 1, count - nums[index + 1], target);
        dfs(index + 1, count + nums[index + 1], target);
    }
}