What is the optimal approach to solve Target Sum efficiently?

The most efficient approach uses state transition dynamic programming, tracking cumulative sums and reducing redundant recursive calls.

Can backtracking alone handle large input arrays?

Backtracking alone is exponential and may time out for arrays near length 20, so DP or memoization is recommended.

How does the presence of zeros in nums affect the solution?

Zeros double the number of valid expressions at their positions, so DP must account for this to avoid undercounting.

Is there a way to convert Target Sum into a subset sum problem?

Yes, by representing the problem as sum(P) - sum(N) = target, you can compute valid subsets whose sum equals (target + totalSum)/2.

What are common mistakes when implementing DP for Target Sum?

Common mistakes include mismanaging negative sums in the DP array, not initializing the base case correctly, and double-counting zeros.

#494

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

目标和

给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个表达式：例如， nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。返回…

数组动态规划回溯

题目描述

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

lightbulb

解题思路

方法一：动态规划

我们记数组 $\textit{nums}$ 所有元素的和为 $s$ ，添加负号的元素之和为 $x$ ，则添加正号的元素之和为 $s - x$ ，则有：

(s - x) - x = \textit{target} \Rightarrow x = \frac{s - \textit{target}}{2}

由于 $x \geq 0$ ，且 $x$ 为整数，所以 $s \geq \textit{target}$ 且 $s - \textit{target}$ 为偶数。如果不满足这两个条件，则直接返回 $0$ 。

接下来，我们可以将问题转化为：在数组 $\textit{nums}$ 中选取若干元素，使得这些元素之和等于 $\frac{s - \textit{target}}{2}$ ，问有多少种选取方法。

我们可以使用动态规划来解决这个问题。定义 $f[i][j]$ 表示在数组 $\textit{nums}$ 的前 $i$ 个元素中选取若干元素，使得这些元素之和等于 $j$ 的选取方案数。

对于 $\textit{nums}[i - 1]$ ，我们有两种选择：选取或不选取。如果我们不选取 $\textit{nums}[i - 1]$ ，则 $f[i][j] = f[i - 1][j]$ ；如果我们选取 $\textit{nums}[i - 1]$ ，则 $f[i][j] = f[i - 1][j - \textit{nums}[i - 1]]$ 。因此，状态转移方程为：

f[i][j] = f[i - 1][j] + f[i - 1][j - \textit{nums}[i - 1]]

其中，选取的前提是 $j \geq \textit{nums}[i - 1]$ 。

最终答案即为 $f[m][n]$ 。其中 $m$ 为数组 $\textit{nums}$ 的长度，而 $n = \frac{s - \textit{target}}{2}$ 。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        s = sum(nums)
        if s < target or (s - target) % 2:
            return 0
        m, n = len(nums), (s - target) // 2
        f = [[0] * (n + 1) for _ in range(m + 1)]
        f[0][0] = 1
        for i, x in enumerate(nums, 1):
            for j in range(n + 1):
                f[i][j] = f[i - 1][j]
                if j >= x:
                    f[i][j] += f[i - 1][j - x]
        return f[m][n]

speed

复杂度分析

指标	值
时间	complexity is O(n \cdot totalSum) since each number updates sums in DP. Space complexity is O(totalSum) because only two layers of DP are needed for state transitions.
空间	O(2 \cdot \text{totalSum}) \approx O(\text{totalSum})

psychology

面试官常问的追问

外企场景

question_mark
Check if candidates recognize the combinatorial nature and naive exponential backtracking.
question_mark
Notice whether they optimize using memoization or DP for cumulative sum tracking.
question_mark
Observe handling of zeros and negative targets in expressions.

warning

常见陷阱

外企场景

error
Failing to handle zeros correctly, which can double-count certain expressions if not treated in DP.
error
Ignoring negative cumulative sums in DP, causing index errors or missed combinations.
error
Attempting pure backtracking without memoization, leading to timeouts for arrays near length 20.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Count expressions using only '+' signs that reach half the total sum of nums.
arrow_right_alt
Modify the problem to allow multiplication or division signs with similar state tracking.
arrow_right_alt
Return all valid expressions as strings instead of just the count, emphasizing backtracking construction.

help

常见问题

外企场景

继续练习

#473 火柴拼正方形 #526 优美的排列 #638 大礼包