手撕算法：一个整数序列array和一个整数n，请你统计并返回该序列中和为n的子序列个数（子序列是序列中元素的非空序列）？

# 1) 是否是 LeetCode 原题？ **不是**现成的 LeetCode 原题。题意是：统计**和为 n 的非空子序列**个数（保持原顺序、每个元素最多用一次）。 **相近参考题（可说明思路来源）：** * **494. Target Sum**：加 +/- 号求目标和（不是直接选/不选的子序列计数）。 * **518. Coin Change II**：组合计数、可重复使用、顺序无关（与本题不同）。 * **416. Partition Equal Subset Sum**：判定型，不计数。 * **879. Profitable Schemes**：带多维约束的子集计数。 > 因此：本题用“**子序列计数**”的 DP 思路实现，和 494/518 的 DP 技巧很像，但模型不同。 # 2) 解法总览（根据数据特点选一套） * **通用解（允许负数/0/正数）**：哈希表滚动 DP（参考 494 的“滚动状态”思想）。 * **优化解（全为非负 & 目标 n 不大）**：一维背包 DP（参考 518 的“倒序更新”技巧，但注意我们**不计空子序列**）。 ## 解法 A：通用版（负/零/正均可）——哈希表滚动 DP **核心**：`ways[sum]` = 截止当前元素，和为 `sum` 的**非空**子序列个数。 扫描元素 `x` 时： * 把 `x` 接到已有所有方案尾部：`sum → sum + x` * 新开一个只含 `x` 的子序列：`x → +1` 用临时 `add` 存本轮新增，合并进 `ways`，避免同轮重复用 `x`。 ### Python ```python def count_subseq_sum(arr, target): ways = {} # sum -> count（非空） for x in arr: add = {} for s, c in ways.items(): add[s + x] = add.get(s + x, 0) + c # 续接 add[x] = add.get(x, 0) + 1 # x 单独 for s, c in add.items(): ways[s] = ways.get(s, 0) + c return ways.get(target, 0) ``` ### Java ```java import java.util.*; public class Solution { public long countSubseqSum(int[] arr, int target) { Map<Integer, Long> ways = new HashMap<>(); // sum -> count（非空） for (int x : arr) { Map<Integer, Long> add = new HashMap<>(); for (Map.Entry<Integer, Long> e : ways.entrySet()) { int ns = e.getKey() + x; add.put(ns, add.getOrDefault(ns, 0L) + e.getValue()); // 续接 } add.put(x, add.getOrDefault(x, 0L) + 1L); // x 单独 for (Map.Entry<Integer, Long> e : add.entrySet()) { ways.put(e.getKey(), ways.getOrDefault(e.getKey(), 0L) + e.getValue()); } } return ways.getOrDefault(target, 0L); } } ``` * **正确性对齐“子序列”**：我们从左到右扫描，仅允许把当前元素追加到已有方案尾部或单独成新序列，保证按原顺序、每个元素最多用一次。 * **复杂度**：设可达的不同和数量为 `K`，时间/空间约 `O(n·K)`（最坏可能较大，这是含负数时的本质复杂度）。 ## 解法 B：全为非负 & n 不大——一维背包 DP 参考 518 的倒序更新技巧，但**不计空子序列**，因此不要设 `dp[0]=1`。 `dp[s]` = 和为 `s` 的**非空**子序列个数。 ### Python ```python def count_subseq_sum_nonneg(arr, target): dp = [0] * (target + 1) # 不初始化 dp[0]=1，避免把空集算进来 for x in arr: if x <= target: for s in range(target, x - 1, -1): dp[s] += dp[s - x] # 续接旧方案 dp[x] += 1 # x 单独成序列 return dp[target] ``` * **复杂度**：`O(n·target)` 时间，`O(target)` 空间。 * **适用前提**：数组元素**都 ≥ 0**，否则倒序背包不成立。 ## 小样例自检 * `arr = [1, 2, 1], n = 3` 有效子序列（保持原顺序）：`[1,2]`、`[2,1]`、`[1,1,1]` → **3**。 * `arr = [0, 0], n = 0`（允许 0） 非空子序列：`[0]`、`[0]`、`[0,0]` → **3**（通用版能正确计数）。