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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find the Sum of the Power of All Subsequences

Number: 3345

Difficulty: Hard

Paid? No

Companies: DE Shaw

Problem Description

Given an integer array nums and a positive integer k, the power of an array is defined as the number of its subsequences (not necessarily contiguous) that sum exactly to k. The task is to calculate the sum of the power over all subsequences of nums. Since the answer can be very large, return it modulo 10^9 + 7.

Key Insights

  • Notice that each subsequence X of nums contributes the count of its own sub-subsequences Y with sum(Y) == k.
  • Reorder the summation. Instead of iterating over every subsequence X and then counting valid Y ⊆ X, we can first choose Y ⊆ nums with sum k and then count in how many supersets X (of nums) the chosen Y appears.
  • For a fixed valid subset Y with sum k and |Y| = t, any subsequence X that contains Y is obtained by choosing an arbitrary subset from the remaining (n – t) elements. There are 2^(n – t) such choices.
  • Hence the answer becomes the sum over all subsets Y ⊆ nums such that sum(Y)==k of 2^(n – |Y|).
  • Use dynamic programming to count, for each possible subset Y (by tracking current sum and the number t of elements chosen), the number of ways to achieve each sum.
  • Finally, multiply each count with the corresponding power weight 2^(n-t) and take the result modulo 10^9+7.

Space and Time Complexity

Time Complexity: O(n * k * n) = O(n^2 * k) since we iterate over each element and update DP for sums up to k and count up to n. Space Complexity: O(k * n) for the DP table.

Solution

We reformulate the double counting as follows. Instead of summing the power for every subsequence X, we reverse the order and sum over every possible subsequence Y of nums which has sum exactly k. For each such Y (with |Y| = t), its contribution is 2^(n – t) because any superset X (with Y ⊆ X ⊆ nums) will “inherit” the subsequence Y.

We perform a DP where dp[s][t] counts the number of ways to pick t elements (from some prefix of nums) that sum to s. Initialize dp[0][0] = 1. For every number in nums, update the DP: for every (s, t) we accumulate ways such that if adding the current number does not exceed k, update dp[s + num][t + 1]. After processing all elements, the answer is the sum for all t of dp[k][t] * (2^(n-t)) modulo 10^9+7.

The main trick is the “swap” of summation order so that we avoid iterating over all subsequences of nums (2^n possibilities) explicitly.

Code Solutions

#!/usr/bin/env python3
MOD = 10**9 + 7

def sum_power_of_all_subsequences(nums, k):
    n = len(nums)
    # dp[s][t] = number of ways to have sum s with exactly t numbers
    dp = [[0]*(n+1) for _ in range(k+1)]
    dp[0][0] = 1  # one way to sum to 0 with 0 elements

    # iterate over each number in the array
    for num in nums:
        # we iterate backwards to avoid using updated values too early
        for s in range(k, -1, -1):
            for t in range(n-1, -1, -1):
                if dp[s][t] != 0 and s + num <= k:
                    dp[s + num][t + 1] = (dp[s + num][t + 1] + dp[s][t]) % MOD

    # Precompute powers of 2: pow2[i] = 2^i % MOD
    pow2 = [1] * (n+1)
    for i in range(1, n+1):
        pow2[i] = (pow2[i-1] * 2) % MOD

    result = 0
    # for every valid subset Y (with sum == k) count how many supersets X contain Y
    for t in range(0, n+1):
        result = (result + dp[k][t] * pow2[n - t]) % MOD
    return result

# Example usage:
nums = [1,2,3]
k = 3
print(sum_power_of_all_subsequences(nums, k))
← Back to All Questions