We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find the Sum of the Power of All Subsequences

Difficulty: Hard

Problem Description

You are given an integer array nums of length n and a positive integer k. The power of an array of integers is defined as the number of subsequences with their sum equal to k. Return the sum of the power of all subsequences of nums. Since the answer may be very large, return it modulo 10^9 + 7.

Key Insights

  • Each subsequence of nums can contribute to the total power if its sum equals k.
  • The number of subsequences that sum to k can vary depending on the elements chosen.
  • A dynamic programming approach can efficiently count the number of ways to achieve the sum k using the elements of nums.
  • The total power can be calculated by considering the contribution of each subsequence separately.

Space and Time Complexity

Time Complexity: O(n * k), where n is the length of nums and k is the target sum. Space Complexity: O(k), for storing the counts of subsequences that sum to each value from 0 to k.

Solution

The solution utilizes dynamic programming to count the number of subsequences that sum to k. We maintain a DP array where dp[j] represents the number of ways to achieve the sum j using the elements processed so far. For each element in nums, we iterate through the possible sums in reverse to avoid overwriting results from the current iteration. The contribution of each subsequence is summed to derive the total power.

Code Solutions

def sum_of_power_subsequences(nums, k):
    MOD = 10**9 + 7
    n = len(nums)
    
    # DP array to count subsequences summing to each value
    dp = [0] * (k + 1)
    dp[0] = 1  # One way to achieve sum 0: use the empty subsequence

    for num in nums:
        # Traverse backwards to avoid overwriting results from this round
        for j in range(k, num - 1, -1):
            dp[j] = (dp[j] + dp[j - num]) % MOD

    total_power = 0
    # Calculate total power by summing contributions of all subsequences
    for num in nums:
        total_power = (total_power + dp[k]) % MOD

    return total_power
← Back to All Questions