Skip to content

Latest commit

 

History

History
168 lines (102 loc) · 8.37 KB

3082.find-the-sum-of-the-power-of-all-subsequences.md

File metadata and controls

168 lines (102 loc) · 8.37 KB
Raw

题目地址(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 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

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