Hard

题目描述

给定一个长度为 n 的整数数组 nums 和一个正整数 k。

数组的幂定义为和等于 k 的子序列的数量。

返回 nums 所有子序列的幂之和。

由于答案可能很大，请返回对 10^9 + 7 取模的结果。

示例 1：

输入：nums = [1,2,3], k = 3
输出：6
解释：

nums 有 5 个非零幂的子序列：

  • 子序列 [1,2,3] 有 2 个和等于 3 的子序列：[1,2] 和 [3]
  • 子序列 [1,2] 有 1 个和等于 3 的子序列：无
  • 子序列 [1,3] 有 1 个和等于 3 的子序列：无
  • 子序列 [2,3] 有 1 个和等于 3 的子序列：无
  • 子序列 [3] 有 1 个和等于 3 的子序列：[3]

因此答案是 2 + 1 + 1 + 1 + 1 = 6。

示例 2：

输入：nums = [2,3,3], k = 5
输出：4

示例 3：

输入：nums = [1,2,3], k = 7
输出：0
解释：不存在和为 7 的子序列，因此所有子序列的幂都为 0。

提示：

  • 1 <= n <= 100
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 100

解题思路

这是一道关于动态规划和组合数学的题目。核心思想是理解子序列的幂的定义，并利用数学性质优化计算。

关键观察：

  1. 对于原数组的每个子序列，其幂等于该子序列中和等于k的子子序列数量
  2. 如果一个长度为j的子序列和等于k，那么包含这个子序列的所有原数组子序列都会对答案贡献1
  3. 长度为j且和等于k的子序列，会被包含在2^(n-j)个原数组的子序列中

算法思路： 使用三维DP：dp[i][j][sum] 表示前i个元素中，选择j个元素，和为sum的方案数。

但考虑到空间优化，我们可以使用二维DP：dp[j][sum] 表示当前考虑的元素集合中，选择j个元素，和为sum的方案数。

对于每个长度j，我们计算dp[j][k]的值，然后乘以2^(n-j)（表示剩余n-j个元素可选可不选），累加到答案中。

推荐解法： 二维DP + 组合数学

代码实现

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        
        // dp[j][sum] = 选择j个元素，和为sum的方案数
        vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
        dp[0][0] = 1; // 不选任何元素，和为0
        
        // 计算2的幂次
        vector<long long> pow2(n + 1);
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }
        
        for (int num : nums) {
            // 倒序遍历，避免重复计算
            for (int j = n; j >= 1; j--) {
                for (int sum = k; sum >= num; sum--) {
                    dp[j][sum] = (dp[j][sum] + dp[j - 1][sum - num]) % MOD;
                }
            }
        }
        
        long long result = 0;
        for (int j = 1; j <= n; j++) {
            result = (result + dp[j][k] * pow2[n - j]) % MOD;
        }
        
        return result;
    }
};

class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # dp[j][sum] = 选择j个元素，和为sum的方案数
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        dp[0][0] = 1  # 不选任何元素，和为0
        
        # 计算2的幂次
        pow2 = [1] * (n + 1)
        for i in range(1, n + 1):
            pow2[i] = (pow2[i - 1] * 2) % MOD
        
        for num in nums:
            # 倒序遍历，避免重复计算
            for j in range(n, 0, -1):
                for s in range(k, num - 1, -1):
                    dp[j][s] = (dp[j][s] + dp[j - 1][s - num]) % MOD
        
        result = 0
        for j in range(1, n + 1):
            result = (result + dp[j][k] * pow2[n - j]) % MOD
        
        return result

public class Solution {
    public int SumOfPower(int[] nums, int k) {
        const int MOD = 1000000007;
        int n = nums.Length;
        
        // dp[j,sum] = 选择j个元素，和为sum的方案数
        long[,] dp = new long[n + 1, k + 1];
        dp[0, 0] = 1; // 不选任何元素，和为0
        
        // 计算2的幂次
        long[] pow2 = new long[n + 1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = (pow2[i - 1] * 2) % MOD;
        }
        
        foreach (int num in nums) {
            // 倒序遍历，避免重复计算
            for (int j = n; j >= 1; j--) {
                for (int sum = k; sum >= num; sum--) {
                    dp[j, sum] = (dp[j, sum] + dp[j - 1, sum - num]) % MOD;
                }
            }
        }
        
        long result = 0;
        for (int j = 1; j <= n; j++) {
            result = (result + dp[j, k] * pow2[n - j]) % MOD;
        }
        
        return (int)result;
    }
}

var sumOfPower = function(nums, k) {
    const MOD = 1e9 + 7;
    const n = nums.length;
    
    // dp[j][sum] = 选择j个元素，和为sum的方案数
    const dp = Array(n + 1).fill().map(() => Array(k + 1).fill(0));
    dp[0][0] = 1; // 不选任何元素，和为0
    
    // 计算2的幂次
    const pow2 = new Array(n + 1);
    pow2[0] = 1;
    for (let i = 1; i <= n; i++) {
        pow2[i] = (pow2[i - 1] * 2) % MOD;
    }
    
    for (const num of nums) {
        // 倒序遍历，避免重复计算
        for (let j = n; j >= 1; j--) {
            for (let sum = k; sum >= num; sum--) {
                dp[j][sum] = (dp[j][sum] + dp[j - 1][sum - num]) % MOD;
            }
        }
    }
    
    let result = 0;
    for (let j = 1; j <= n; j++) {
        result = (result + dp[j][k] * pow2[n - j]) % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²k)
空间复杂度O(nk)

其中 n 是数组长度，k 是目标和。时间复杂度主要来自于三层循环：遍历数组元素、长度和和值。空间复杂度来自于二维DP数组的存储。

相关题目