LeetCode 题解工作台
求出所有子序列的能量和
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。 一个整数数组的 能量 定义为和 等于 k 的子序列的数目。 请你返回 nums 中所有子序列的 能量和 。 由于答案可能很大，请你将它对 10 9 + 7 取余 后返回。 示例 1： 输入： nums = [1,2,3], k = …
2
题型
5
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
题目需要我们在给定数组 中找到所有子序列 ，然后计算每个 的每个子序列 的和等于 的方案数。 我们定义 表示前 个数构成的若干个子序列中，每个子序列的子序列和等于 的方案数。初始时 $f[0][0] = 1$，其余位置均为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你一个长度为 n 的整数数组 nums 和一个 正 整数 k 。
一个整数数组的 能量 定义为和 等于 k 的子序列的数目。
请你返回 nums 中所有子序列的 能量和 。
由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入： nums = [1,2,3], k = 3
输出： 6
解释：
总共有 5 个能量不为 0 的子序列：
- 子序列
[1,2,3]有2个和为3的子序列：[1,2,3]和[1,2,3]。 - 子序列
[1,2,3]有1个和为3的子序列：[1,2,3]。 - 子序列
[1,2,3]有1个和为3的子序列：[1,2,3]。 - 子序列
[1,2,3]有1个和为3的子序列：[1,2,3]。 - 子序列
[1,2,3]有1个和为3的子序列：[1,2,3]。
所以答案为 2 + 1 + 1 + 1 + 1 = 6 。
示例 2：
输入： nums = [2,3,3], k = 5
输出： 4
解释：
总共有 3 个能量不为 0 的子序列：
- 子序列
[2,3,3]有 2 个子序列和为5：[2,3,3]和[2,3,3]。 - 子序列
[2,3,3]有 1 个子序列和为5：[2,3,3]。 - 子序列
[2,3,3]有 1 个子序列和为5：[2,3,3]。
所以答案为 2 + 1 + 1 = 4 。
示例 3：
输入： nums = [1,2,3], k = 7
输出： 0
解释：不存在和为 7 的子序列，所以 nums 的能量和为 0 。
提示：
1 <= n <= 1001 <= nums[i] <= 1041 <= k <= 100
解题思路
方法一：动态规划
题目需要我们在给定数组 中找到所有子序列 ，然后计算每个 的每个子序列 的和等于 的方案数。
我们定义 表示前 个数构成的若干个子序列中，每个子序列的子序列和等于 的方案数。初始时 ，其余位置均为 。
对于第 个数 ，有以下三种情况：
- 不在子序列 中，此时 ；
- 在子序列 ，但不在子序列 中，此时 ；
- 在子序列 ，且在子序列 中，此时 。
综上，状态转移方程为：
最终答案为 。
时间复杂度 ，空间复杂度 。其中 为数组 的长度，而 为给定的正整数。
class Solution:
def sumOfPower(self, nums: List[int], k: int) -> int:
mod = 10**9 + 7
n = len(nums)
f = [[0] * (k + 1) for _ in range(n + 1)]
f[0][0] = 1
for i, x in enumerate(nums, 1):
for j in range(k + 1):
f[i][j] = f[i - 1][j] * 2 % mod
if j >= x:
f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod
return f[n][k]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The problem tests knowledge of dynamic programming and subset sum problems.
- question_mark
Candidates should demonstrate understanding of state transitions in dynamic programming.
- question_mark
Pay attention to how the solution scales with n and k, as efficiency is key for larger inputs.
常见陷阱
外企场景- error
Misunderstanding the contribution of subsequences to the power sum.
- error
Failing to update the DP table correctly during iteration.
- error
Not handling edge cases such as when no subsequence sums to k, resulting in zero power.
进阶变体
外企场景- arrow_right_alt
Consider modifying the problem by changing the target sum k or adding constraints like limiting subsequence length.
- arrow_right_alt
What if the array contains duplicates or the integers in nums have different ranges?
- arrow_right_alt
Extend the problem to handle multiple target sums, requiring the calculation of power for each.