带正负号的目标和
将目标和赋值问题转换为关于子集和差值的背包问题，并在 O(n × sum) 时间内求解。
带正负号的目标和 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 4 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
目标和问题
给定一个整数数组 nums 和一个整数 target，为每个数字分配 + 或 - 符号，使最终表达式的计算结果等于 target。请返回实现这一目标的不同方式数量。例如，对于 nums=[1,1,1,1,1] 和 target=3，共有 5 种方式（选择 4 个元素为正，选择 1 个元素为负，且负号所在位置不同）。
暴力法：DFS 枚举
DFS 方法为每个数字分配 + 或 -，然后递归处理，并返回最终达到 target 的叶节点数量。这种方法是正确的，但时间复杂度为O(2^n)，也就是指数级复杂度。当 n=20 时，需要进行一百多万次递归调用。面试中值得先提到 DFS 方法，然后迅速转向 DP 优化。
def findTargetSumWays_dfs(nums, target):
count = [0]
def dfs(i, current_sum):
if i == len(nums):
if current_sum == target:
count[0] += 1
return
dfs(i+1, current_sum + nums[i])
dfs(i+1, current_sum - nums[i])
dfs(0, 0)
return count[0]
print(findTargetSumWays_dfs([1,1,1,1,1], 3)) # 5记忆化 DFS
为 DFS 添加记忆化：状态为 (index, current_sum)。由于 current_sum 的范围可以从 -total 到 +total，因此共有 O(n × total) 个不同状态。加入记忆化后，DFS 的时间和空间复杂度均为O(n × total)。这种方法可行，在面试中使用也没有问题，但基于变换的 DP 更简洁，并且更节省空间。
from functools import lru_cache
def findTargetSumWays_memo(nums, target):
total = sum(nums)
@lru_cache(maxsize=None)
def dp(i, remaining):
if i == len(nums):
return 1 if remaining == 0 else 0
return dp(i+1, remaining - nums[i]) + dp(i+1, remaining + nums[i])
return dp(0, target)
print(findTargetSumWays_memo([1,1,1,1,1], 3)) # 5数学变换
设被分配 + 的数字集合为 P，被分配 - 的数字集合为 N。那么：sum(P) - sum(N) = target，且 sum(P) + sum(N) = total。将两式相加：2 × sum(P) = target + total，因此 sum(P) = (target + total) / 2。问题就变成：统计 nums 中和为 (target + total) / 2 的子集数量。这正是 0/1 背包中“统计子集数量”的变体。
# sum(P) - sum(N) = target
# sum(P) + sum(N) = total
# => 2*sum(P) = target + total
# => sum(P) = (target + total) / 2
# Count subsets with sum = new_target = (target + total) // 2
print('Reduction: count subsets summing to (target + total) // 2')运行 DP 前的有效性检查
运行 DP 之前，请检查：(1) target + total 必须是偶数（否则 sum(P) 不是整数，问题无解）；(2) abs(target) > total 表示即使所有符号方向一致，也无法得到该目标值。如果任一检查失败，就立即返回 0。这些检查可以简洁地处理边界情况，无需在 DP 循环内部添加特殊逻辑。
def findTargetSumWays(nums, target):
total = sum(nums)
if (target + total) % 2 != 0:
return 0 # sum(P) would be non-integer
if abs(target) > total:
return 0 # impossible to reach
new_target = (target + total) // 2
# Count subsets summing to new_target
dp = [0] * (new_target + 1)
dp[0] = 1
for num in nums:
for c in range(new_target, num - 1, -1):
dp[c] += dp[c - num]
return dp[new_target]
print(findTargetSumWays([1,1,1,1,1], 3)) # 5小示例推演
对于 nums=[1,1,1,1,1]、target=3：total=5，new_target=(3+5)//2=4。我们要统计 [1,1,1,1,1] 中和为 4 的子集数量。这就是 C(5,4)=5（选择 4 个 1 为正，第 5 个为负：1+1+1+1-1=3）。DP 正确返回 5。这个变换巧妙地将符号分配问题映射为标准的子集计数问题。
处理 nums 中的零
如果 nums 中包含零，为零分配 + 或 - 都不会改变总和。每个零都会使有效分配数量翻倍。DP 会自然地处理这种情况：处理 num=0 时，内层循环 range(new_target, -1, -1) 会从 new_target 递减到 0，并且 dp[c] += dp[c - 0] = dp[c] 会使所有可达和的计数翻倍。如果使用从 new_target 递减到 0 的 range(new_target, num-1, -1)，则无需进行特殊处理，因为 num=0 时它会遍历到 0。
# With zeros: each zero doubles the count
print(findTargetSumWays([0, 0, 1], 1)) # 4
# Assignments: +0+0+1, +0-0+1, -0+0+1, -0-0+1 = all give sum 1复杂度比较
暴力 DFS 的复杂度为O(2^n)。记忆化 DFS 的时间复杂度和空间复杂度均为O(n × total)。基于变换的一维 DP 的时间复杂度为O(n × new_target)，空间复杂度为O(new_target)，其中 new_target ≤ total。由于通过变换消除了索引这一维度，一维 DP 比记忆化方法使用的空间显著更少。
与其他背包问题的联系
目标和将多个背包概念联系在一起：它起初是一个分配问题，之后变换为子集和问题（类似 Partition Equal Subset Sum），并使用相同的 0/1 背包反向遍历模板进行计数（类似 Coin Change II）。掌握这些联系后，您就能在面试中根据新问题与已知模式的结构相似性，快速判断问题类型。
边界情况与面试要点
关键情况包括：(1) target = total：只有一种方式（全部为正）；(2) target = -total：只有一种方式（全部为负）；(3) target = 0 且全部为零：答案为 2^n；(4) total 非常大但 n 较小——一维 DP 数组的大小上限为 total/2。面试时，请先口头讲解变换步骤，再开始编码——这是最不直观的关键洞察，也是区分优秀候选人的要点。
不进行变换的二维 DP 方案
不使用变换时，可以定义 dp[i][s]，表示为前 i 个数字分配符号并使总和达到 s 的方式数量。由于总和可能为负数，因此使用 total 进行偏移：使用 dp[i][s + total]。这需要一个大小为 (n+1) × (2*total+1) 的二维表。虽然这种方法是正确的，但它占用更多空间，而且在面试压力下，比变换后的一维背包更难快速编码。
快速检查
请检验您对本课程中“数据结构与算法——编程面试准备”相关概念的理解。
课程回顾
在本课中，您学到了：目标和问题可通过变换，转化为统计和为 (target + total) / 2 的子集数量，一维 0/1 背包通过反向遍历，在 O(n × new_target) 时间和 O(new_target) 空间内统计子集数量，以及提前进行有效性检查（和为奇数、|target| > total）可以避免不必要的 DP 执行。接下来我们将进入最短路径领域，学习 Dijkstra 算法和优先队列。
常见问题解答
「带正负号的目标和」课时是免费的吗？
是的 — 「带正负号的目标和」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「带正负号的目标和」这节课中我会学到什么？
将目标和赋值问题转换为关于子集和差值的背包问题，并在 O(n × sum) 时间内求解。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 4 节课，共 4 节。
「带正负号的目标和」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。
此课程中的所有课时
- 0/1 背包与空间优化
- 完全背包与零钱兑换 II
- 等和子集分割
- 带正负号的目标和