LeetCode 补充题 129. 目标和非空子序列计数
题目描述
给你一个非负整数数组
nums和一个整数target，请返回元素和等于target的非空子序列数量。子序列可以不连续，但必须保持原下标的相对顺序。数值相同但下标不同的元素，视为不同的选择。结果使用 64 位整数表示，不需要取模。
示例 1：
输入：
nums = [1,1,2], target = 2
输出：2
解释： 选择前两个 1，或单独选择 2，分别是一种。
示例 2：
输入：
nums = [0,0,0], target = 0
输出：7
解释： 共有 2³ 个下标子集，去掉空集后剩 7 个。
提示：
- 采用长度
1…60的非负整数数组版本。 - 元素和
target均在0…10000。 - 按下标选择计数。
- 结果使用
64位整数；最多2⁶⁰种选择，不需要取模。
题意分析
只要求方案数量，不需要把全部子序列列出来，可以将相同元素和的选择合并计数。数组非负，使状态只需保存
0～target的和；按输入下标逐个处理，天然区分相同值的不同位置。
解法：逆序 0/1 背包计数
核心思路
[!blue]
dp[s]表示已处理前缀中，选出和为s的下标集合数量。初始dp[0] = 1表示空选择，其余为 0，否则第一件物品也没有可扩展的起点。处理值
value时，不选的方案保留在原dp[s]，选择它的方案来自此前的dp[s-value]，两类下标集合不同，所以计数相加。容量从大到小更新，防止当前下标被重复选入。当
value == 0时，更新变成dp[s] += dp[s]，恰好对应选与不选这个零的两种选择，并不是重复计算。全部元素处理完后，仅在target == 0时扣除唯一的空选择；最大计数不超过2^60，用 64 位整数保存。
解题步骤
- 初始化 dp[0]=1 表示空选择。
- 逐个处理元素，目标和从大到小更新，防止一个位置重复使用。
- target=0 时从 dp[0] 扣除空集，其余直接返回目标状态。
代码实现
class Solution {
public long countSubsequences(int[] nums, int target) {
long[] dp = new long[target + 1];
dp[0] = 1;
for (int value : nums) {
for (int sum = target; sum >= value; sum--) {
dp[sum] += dp[sum - value];
}
}
return target == 0 ? dp[0] - 1 : dp[target];
}
}
func countSubsequences(nums []int, target int) int64 {
dp := make([]int64, target+1)
dp[0] = 1
for _, value := range nums {
for sum := target; sum >= value; sum-- {
dp[sum] += dp[sum-value]
}
}
if target == 0 {
return dp[0] - 1
}
return dp[target]
}
复杂度分析
- 时间复杂度：$O(n\cdot (target+1))$。
- 空间复杂度：额外空间 $O(target+1)$。
关键点总结
[!green]
0 元素也有选与不选两种下标方案，会使对应计数翻倍；不能跳过或对元素先去重。
易错点总结
[!yellow]
不能把子序列当成连续子数组；0 也有选与不选两种方案，不能跳过。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 494. 目标和 | 中等 | 原题通过正负号转换为子集和计数，本题直接选择下标，且最后要扣除目标为 0 时的空集。 |
| 416. 分割等和子集 | 中等 | 同样逆序更新 0/1 背包，本题记录方案数，原题仅记录是否可达。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！