目标和

约 1404 字大约 5 分钟

回溯动态规划背包问题

2025-02-26

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 <= 1000

回溯

从数组头开始回溯，结束条件（走到末尾）+选择+进入子递归+撤销选择。

class Solution {
    int result = 0;

    public int findTargetSumWays(int[] nums, int target) {
        if (nums.length == 0) return 0;
        backtrack(nums, 0, target);
        return result;
    }

    void backtrack(int[] nums, int i, int remain) {
        // base case
        if (i == nums.length) {
            if (remain == 0) {
                // 说明恰好凑出 target
                result++;
            }
            return;
        }
        
        // 给 nums[i] 选择 - 号
        remain += nums[i];
        // 穷举 nums[i + 1]
        backtrack(nums, i + 1, remain);
        // 撤销选择
        remain -= nums[i];
        
        // 给 nums[i] 选择 + 号
        remain -= nums[i];
        // 穷举 nums[i + 1]
        backtrack(nums, i + 1, remain);
        // 撤销选择
        remain += nums[i];
    }
}

时间复杂度： $O\left(2^n\right)$ ，其中 $n$ 是数组 nums 的长度。回溯需要遍历所有不同的表达式，共有 $2^n$ 种不同的表达式，每种表达式计算结果需要 $O(1)$ 的时间，因此总时间复杂度是 $O\left(2^n\right)$ 。
空间复杂度： $O(n)$ ，其中 $n$ 是数组 $n u m s$ 的长度。空间复杂度主要取决于递归调用的栈空间，栈的深度不超过 $n$ 。

动态规划，背包问题，分类，和为指定值的子集数量

首先，如果我们把 nums 划分成两个子集 A 和 B，分别代表分配 + 的数和分配 - 的数，那么他们和 target 存在如下关系：

sum(A) - sum(B) = target
sum(A) = target + sum(B)
sum(A) + sum(A) = target + sum(B) + sum(A)
2 * sum(A) = target + sum(nums)

综上，可以推出 sum(A) = (target + sum(nums)) / 2，也就是把原问题转化成：nums 中存在几个子集 A，使得 A 中元素的和为 (target + sum(nums)) / 2？

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int n : nums) sum += n;
        
        // 如果总和小于目标值的绝对值（全部取加号），或者 (sum + target) 是奇数，不可能存在合法的子集划分
        if (sum < Math.abs(target) || (sum + target) % 2 == 1) {
            return 0;
        }

        // 计算子集和为 (sum + target) / 2 的子集数量
        return subsets(nums, (sum + target) / 2);
    }

    // 计算 nums 中有几个子集的和为 sum
    public int subsets(int[] nums, int sum) {
        int n = nums.length;
        // 初始化动态规划数组 dp，dp[i][j] 表示前 i 个数中有多少个子集的和为 j
        int[][] dp = new int[n + 1][sum + 1];
        // base case：前 0 个数中有 1 个子集的和为 0（即空集），第一行和第一列的其余位置都是默认值0。
        // 一定要注意空集。空集的个数是1，大小（即元素个数）是0
        dp[0][0] = 1;

        // 遍历数组。物品。
        for (int i = 1; i <= n; i++) {
            // 遍历所有可能的和。容量。
            for (int j = 0; j <= sum; j++) {
                if (j >= nums[i - 1]) { // 第i个元素的索引是i-1
                    // 当前和 j 大于等于当前数 nums[i-1]，可以选择不选或选这个数。重点。
                    // 因为返回值是子集数量，所以要相加。
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
                } else {
                    // 当前和 j 小于当前数 nums[i-1]，只能选择不选这个数
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        
        return dp[n][sum];
    }
}

时间复杂度: $O(n \times(sum - target))$ ，其中 $n$ 是数组 $nums$ 的长度，sum 是数组 nums 的元素和，target 是目标数。动态规划有 $(n+1) \times\left(\frac{\text { sum } - \text { target }}{2} + 1\right)$ 个状态，需要计算每个状态的值。两个for循环。
空间复杂度: $O(n \times(sum - target))$ ，其中 $n$ 是数组 $nums$ 的长度， sum 是数组 nums 的元素和， target 是目标数。使用二维数组 $dp$ 存储所有状态的值。

动态规划-背包问题，滚动更新，倒序遍历。

然后，发现这个 dp[i][j] 只和前一行 dp[i-1][..] 有关，那么肯定可以优化成一维 dp：

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int n : nums) sum += n;
        
        // 这两种情况，不可能存在合法的子集划分
        if (sum < Math.abs(target) || (sum + target) % 2 == 1) {
            return 0;
        }
        
        return subsets(nums, (sum + target) / 2);
    }

    // 计算 nums 中有几个子集的和为 sum
    public int subsets(int[] nums, int sum) {
        int n = nums.length;
        int[] dp = new int[sum + 1];
        
        // base case
        dp[0] = 1;

        for (int i = 1; i <= n; i++) {
            // j 要从后往前遍历
            for (int j = sum; j >= nums[i - 1]; j--) {
                // 状态转移方程
                dp[j] = dp[j] + dp[j - nums[i - 1]];
            }
        }
        
        return dp[sum];
    }
}

时间复杂度: $O(n \times(sum - target))$ ，其中 $n$ 是数组 $nums$ 的长度， sum 是数组 nums 的元素和， target 是目标数。动态规划有 $(n+1) \times\left(\frac{\text { sum }- \text { target }}{2}+1\right)$ 个状态，需要计算每个状态的值。两个for循环。
空间复杂度: $O(sum - target)$ ，其中 sum 是数组 nums 的元素和， target 是目标数。使用空间优化的实现，需要创建长度为 $\frac{\text { sum }- \text { target }}{2}+1$ 的数组 $dp$ 。