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

题目地址(3082. 求出所有子序列的能量和 - 力扣(LeetCode))

https://leetcode.cn/problems/find-the-sum-of-the-power-of-all-subsequences/

题目描述

给你一个长度为 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. 求出包含某个子序列的子序列的个数

对于第一个问题,本质就是对于每一个元素选择或者不选择,可以通过动态规划相对轻松地求出。伪代码:

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:


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)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我,这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

最后更新于