LeetCode 3082 · 求出所有子序列的能量和 (Go实现) 解题思路这道题的关键是转换问题对每个和为 k 的子序列 S计算它被多少个大子序列 T 包含包含 S 的大子序列 T 数量 2^(n - |S|)其中 n 是数组长度所以答案为所有和为 k 的子序列 S 的 2^(n-|S|) 之和通过动态规划来计算这个和使用 0-1 背包的思想。 动态规划方法二维 DP更容易理解func sumOfPower(nums []int, k int) int { const MOD 1_000_000_007 n : len(nums) // dp[i][j] 表示前 i 个元素和为 j 的子序列的贡献总和 dp : make([][]int, n1) for i : range dp { dp[i] make([]int, k1) } dp[0][0] 1 // 空子序列 for i : 1; i n; i { x : nums[i-1] for j : 0; j k; j { // 不选 nums[i-1] dp[i][j] (dp[i-1][j] * 2) % MOD } for j : x; j k; j { // 选 nums[i-1] dp[i][j] (dp[i][j] dp[i-1][j-x]) % MOD } } return dp[n][k] }一维 DP优化空间func sumOfPower(nums []int, k int) int { const MOD 1_000_000_007 // dp[j] 表示和为 j 的子序列的贡献总和 dp : make([]int, k1) dp[0] 1 // 空子序列 for _, x : range nums { // 从后向前遍历避免重复使用同一个元素 for j : k; j 0; j-- { // 不选当前元素已有子序列贡献翻倍 dp[j] (dp[j] * 2) % MOD // 选当前元素 if j x { dp[j] (dp[j] dp[j-x]) % MOD } } } return dp[k] } 算法复杂度分析算法版本时间复杂度空间复杂度二维DPO(n·k)O(n·k)一维DPO(n·k)O(k) 测试用例验证package main import fmt func main() { // 测试用例 tests : []struct { nums []int k int want int }{ {[]int{1, 2, 3}, 3, 6}, // 示例1 {[]int{2, 3, 3}, 5, 4}, // 示例2 {[]int{1, 1, 1}, 2, 3}, // 示例3 } for i, test : range tests { result : sumOfPower(test.nums, test.k) if result test.want { fmt.Printf(测试用例 %d 通过: nums%v, k%d, 结果%d\n, i1, test.nums, test.k, result) } else { fmt.Printf(测试用例 %d 失败: nums%v, k%d, 期望%d, 实际%d\n, i1, test.nums, test.k, test.want, result) } } } 详细推导过程为什么这样计算对于任意和为 k 的子序列 S长度为 len包含 S 的大子序列 T 个数 2^(n - len)因为 n-len 个不在 S 中的元素每个都可以选或不选所以答案为∑ (对所有 sum(S)k 的子序列 S) 2^(n - |S|)DP 状态转移解释设处理到第 i 个元素不选 nums[i]原有子序列依然存在而且多了一个自由元素位所以贡献 ×2选 nums[i]从 dp[j-x] 转移过来直接累加原有贡献 关键技巧从后往前遍历避免重复使用同一个元素符合 0-1 背包MOD 取模在每一步乘法加法后都要取模防止溢出边界处理j x 时才进行转移防止数组越界 总结这道题的核心是转换视角从计算每个子序列的能量转换为计算每个固定子序列被多少个大子序列包含然后通过0-1背包DP计算带权重的子序列计数最终的一维DP版本是最高效的实现时间和空间复杂度都达到了最优。