494.目标和

题目描述

给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-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

一共有5种方法让最终目标和为3。

题解

回溯算法

回溯算法的关键在于在递归体中需要进行选择, 这个过程就是深度优先遍历, 因为有一个跟随变量, 所以每次选择后都要手动撤回

public class lc494 {
    private int res = 0;

    public int findTargetSumWays(int[] nums, int S) {
        if (nums.length == 0)
            return res;

        backTrack(nums, 0, S);
        return res;
    }

    private void backTrack(int[] nums, int i, int rest) {
        if (i == nums.length) {
            if (rest == 0) {
                res++;
            }
            return;
        }

        // 符号为 -
        rest += nums[i];
        backTrack(nums, i + 1, rest);
        rest -= nums[i];

        // 符号为 +
        rest -= nums[i];
        backTrack(nums, i + 1, rest);
        rest += nums[i];
    }
}

需要回撤的解释为, 传入的rest变量是在调用递归之前改变的, 如果不撤回会影响到本层程序栈的后续递归调用, 如果这样写, 就不用撤回:

因为没有改变rest 的值

// 符号为 -
// rest += nums[i];
backTrack(nums, i + 1, rest + nums[i]);
// rest -= nums[i];

// 符号为 +
// rest -= nums[i];
backTrack(nums, i + 1, rest - nums[i]);
// rest += nums[i];

动态规划