Find the Sum of the Power of All Subsequences

Hard
1650.

Find the Sum of the Power of All Subsequences

Find the Sum of the Power of All Subsequences is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

You are given an integer array nums of length n and a positive integer k.

The power of an array is the number of its subsequences whose elements sum to exactly k. (Subsequences are chosen by index, so equal values at different positions give different subsequences.)

Return the sum of the power of all subsequences of nums. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

Input
nums = [1,2,3], k = 3
Output
6
Explanation
The subsets summing to 3 are [3] and [1,2]. [3] lies inside 4 subsequences of nums and [1,2] inside 2, so the total is 6.

Example 2

Input
nums = [2,3,3], k = 5
Output
4
Explanation
[2,3] using either 3 sums to 5, and each lies inside 2 subsequences: 4.

Example 3

Input
nums = [1,2,3], k = 7
Output
0
Explanation
Nothing sums to 7.

Constraints

  • 1 <= n <= 100
  • 1 <= nums[i] <= 10^4
  • 1 <= k <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var sumOfPower = function(nums, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Sum of the Power of All Subsequences — Solution

Find the Sum of the Power of All Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Find the Sum of the Power of All Subsequences is a hard coding problem on arrays and dynamic programming, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums of length n and a positive integer k.

The power of an array is the number of its subsequences whose elements sum to exactly k. (Subsequences are chosen by index, so equal values at different positions give different subsequences.)

Return the sum of the power of all subsequences of nums. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1

Input: nums = [1,2,3], k = 3
Output: 6
Explanation: The subsets summing to 3 are [3] and [1,2]. [3] lies inside 4 subsequences of nums and [1,2] inside 2, so the total is 6.

Example 2

Input: nums = [2,3,3], k = 5
Output: 4
Explanation: [2,3] using either 3 sums to 5, and each lies inside 2 subsequences: 4.

Example 3

Input: nums = [1,2,3], k = 7
Output: 0
Explanation: Nothing sums to 7.

Constraints

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

Hints for Find the Sum of the Power of All Subsequences

  1. Hint 1

    Swap the order of counting: instead of looping over outer subsequences, count each inner subset T with sum k by how many outer subsequences contain it.

  2. Hint 2

    A subset T of size t is contained in 2^(n - t) subsequences — every other element is free to be in or out.

  3. Hint 3

    Knapsack DP over sums: for each element there are three fates — not in the outer subsequence, in the outer but not in T, or in T. So dp[j] = 2 · dp[j] + dp[j - x].

How to solve Find the Sum of the Power of All Subsequences

The answer counts pairs (outer subsequence S, inner subset T ⊆ S with sum k). Each element independently is outside S, inside S but not in T, or in T — so a knapsack over the sum of T, with weight 2 for the first two fates and a shift for the third, counts every pair once.

Approach

  1. Let dp[j] count pairs (S, T) over the elements processed so far where T sums to j; start with dp[0] = 1.
  2. For each x, update j from k down to 0: dp[j] = 2 · dp[j] + (j ≥ x ? dp[j - x] : 0), modulo 10^9 + 7.
  3. Return dp[k].

Why it works

The power summed over all S is the number of pairs (S, T) with T ⊆ S and sum(T) = k. Deciding each element's fate independently enumerates every such pair exactly once: "not in T" happens in two ways (in S or not), "in T" in one way and adds x to the sum. Iterating j downwards keeps dp[j - x] from the previous element.

Complexity

  • Time — O(n · k)
  • Space — O(k)

Pitfalls

  • Values larger than k can never be in T but still double every count.
  • dp[0] keeps doubling (it counts pairs with empty T) — do not skip j = 0.
  • Reduce modulo 10^9 + 7 at every step; 2 · dp[j] + dp[j - x] stays below 2^32, so 64-bit arithmetic is enough.

Reference solution

Python

from typing import List

def sumOfPower(nums: List[int], k: int) -> int:
    MOD = 10**9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for x in nums:
        for j in range(k, -1, -1):
            dp[j] = (2 * dp[j] + (dp[j - x] if j >= x else 0)) % MOD
    return dp[k]

Java

public static int sumOfPower(int[] nums, int k) {
    final long MOD = 1000000007L;
    long[] dp = new long[k + 1];
    dp[0] = 1;
    for (int x : nums) {
        for (int j = k; j >= 0; j--) dp[j] = (2 * dp[j] + (j >= x ? dp[j - x] : 0)) % MOD;
    }
    return (int) dp[k];
}

C++

int sumOfPower(vector<int>& nums, int k) {
    const long long MOD = 1000000007LL;
    vector<long long> dp(k + 1, 0);
    dp[0] = 1;
    for (int x : nums) {
        for (int j = k; j >= 0; j--) dp[j] = (2 * dp[j] + (j >= x ? dp[j - x] : 0)) % MOD;
    }
    return (int) dp[k];
}

JavaScript

var sumOfPower = function(nums, k) {
    var MOD = 1000000007;
    var dp = new Array(k + 1).fill(0);
    dp[0] = 1;
    for (var i = 0; i < nums.length; i++) {
        var x = nums[i];
        for (var j = k; j >= 0; j--) dp[j] = (2 * dp[j] + (j >= x ? dp[j - x] : 0)) % MOD;
    }
    return dp[k];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming