如何构造无相等子序列和的n个正整数数组？及制表法子问题

1. 子序列和全唯一时，记忆化递归的时间复杂度是否为O(2^N)？ #

是的。记忆化优化的核心是消除重叠子问题——当多个递归路径会到达相同的状态（当前处理到第i个元素，累计和为s）时，缓存结果避免重复计算。但如果所有子序列的和都唯一，意味着每个递归调用的状态（i, s）都是独一无二的，没有任何重叠子问题，缓存完全无法发挥作用，此时记忆化递归的时间复杂度和暴力递归一致，为O(2^N)。

2. 构造无重复子序列和的正整数数组 #

最简单且通用的构造方法是使用2的幂次数组：[1, 2, 4, 8, ..., 2^(n-1)]。

• 原理：每个数的二进制表示只有一个1，不同子序列对应不同的二进制组合，因此它们的和必然唯一。例如n=3时，数组[1,2,4]的所有子序列和为0（空序列）、1、2、3、4、5、6、7，无重复。
• 更通用的构造规则：每个元素的值大于前面所有元素的和，比如[1, 3, 7, 15, ...]（每个元素为2^i -1）。因为任意子序列若包含当前最大元素，其和必然大于不包含该元素的所有子序列和，因此不可能出现重复的和。

3. 制表法（迭代DP）时间复杂度降低的原因及学习资源 #

时间复杂度降低的核心原因 #

制表法是自底向上的动态规划，它不枚举所有子序列，而是通过状态转移复用计算结果：

• 定义dp[s]为布尔值，表示是否能得到和为s的子序列。
• 初始化dp[0] = true（空序列的和为0）。
• 遍历每个数组元素num，从k倒序遍历到num，更新dp[s] = dp[s] || dp[s - num]（即若s - num可达，则s也可达）。

这个过程中，我们只需要处理N*K个状态（N为数组长度，K为目标和），每个状态仅计算一次。即使存在大量子序列，我们只关心每个和是否可达，而不需要追踪每个子序列的具体路径，因此时间复杂度固定为O(N*K)，不受子序列和是否重复的影响。

学习资源推荐 #

• 《算法导论》动态规划章节：详细讲解0-1背包（子序列和问题属于0-1背包变种）的迭代解法，分析状态转移中如何合并重复子问题。
• 国内高校算法公开课（如中国大学MOOC、学堂在线的算法课程）：多数课程会以子序列和/背包问题为案例，逐步演示制表法的状态计算过程，直观展示哪些子问题被合并处理。
• LeetCode官方题解：例如第416题「分割等和子集」的题解，包含制表法的完整步骤，能清晰看到状态转移如何覆盖所有可能的和，而非枚举子序列。

内容的提问来源于stack exchange，提问作者Anurag Prasad