Question

3082. 求出所有子序列的能量和

English Version

题目描述

给你一个长度为 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 <= 100
• 1 <= nums[i] <= 104
• 1 <= k <= 100

解法

方法一