调试中...
困难
相关标签
相关企业
提示
给你一个长度为 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
通过次数
4.2K
提交次数
9K
通过率
46.4%
相关企业
提示 1
If there is a subsequence of length
j with the sum of elements k, it contributes 2n - j to the answer.提示 2
Let
dp[i][j] represent the number of subsequences in the subarray nums[0..i] which have a sum of j.提示 3
We can find the
dp[i][k] for all 0 <= i <= n-1 and multiply them with 2n - j to get final answer.相似题目
评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线