> For the complete documentation index, see [llms.txt](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/3082.find-the-sum-of-the-power-of-all-subsequences.md).
# 3082. 求出所有子序列的能量和
### 题目地址(3082. 求出所有子序列的能量和 - 力扣（LeetCode）)
### 题目描述
给你一个长度为 `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`
### 前置知识
* 动态规划
### 公司
* 暂无
### 思路
主页里我提到过：“困难题目，从逻辑上说， 要么就是非常难想到，要么就是非常难写代码。 由于有时候需要组合多种算法，因此这部分题目的难度是最大的。”
这道题我们可以先尝试将问题分解，分解为若干相对简单的子问题。然后子问题合并求解出最终的答案。
比如我们可以先`求出和为 k 的子序列`，然后用**贡献法**的思想考虑当前和为 k 的子序列（不妨记做S）对答案的贡献。其对答案的贡献就是**有多少子序列T包含当前和为k的子序列S**。假设有 10 个子序列包含 S，那么子序列 S 对答案的贡献就是 10。
那么问题转化为了：
1. 求出和为 k 的子序列
2. 求出包含某个子序列的子序列的个数
对于第一个问题，本质就是对于每一个元素选择或者不选择，可以通过动态规划相对轻松地求出。伪代码：
```py
def f(i, k):
if i == n:
if k == 0: 找到了
else: 没找到
if k == 0:
没找到
f(i + 1, k) # 不选择
f(i + 1, k - nums[i]) # 选择
```
对于第二个问题，由于除了 S，**其他元素**都可以选择或者不选择，因此总共有 $2^{n-cnt}$ 种选择。其中 cnt 就是子序列 S 的长度。
两个问题结合起来，就可以求出答案了。具体可以看下面的代码。
### 关键点
* 分解问题
### 代码
* 语言支持：Python3
Python3 Code:
```python
class Solution:
def sumOfPower(self, nums: List[int], k: int) -> int:
n = len(nums)
MOD = 10 ** 9 + 7
@cache
def dfs(i, k):
if k == 0: return pow(2, n - i, MOD)
if i == n or k < 0: return 0
ans = dfs(i + 1, k) * 2 # 不选
ans += dfs(i + 1, k - nums[i]) # 选
return ans % MOD
return dfs(0, k)
```
**复杂度分析**
令 n 为数组长度。
由于转移需要 O(1) 的时间，因此总时间复杂度为 O(n \* k)，除了存储递归结果的空间外，没有其他空间消耗，因此空间复杂度为 O(n \* k)。
* 时间复杂度：$O(n \* k)$
* 空间复杂度：$O(n \* k)$
> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。
力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~
以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
