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 <= 1001 <= nums[i] <= 10^41 <= k <= 100
Hints for Find the Sum of the Power of All Subsequences
Hint 1
Swap the order of counting: instead of looping over outer subsequences, count each inner subset
Twith sumkby how many outer subsequences contain it.Hint 2
A subset
Tof sizetis contained in2^(n - t)subsequences — every other element is free to be in or out.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 inT. Sodp[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
- Let
dp[j]count pairs (S, T) over the elements processed so far where T sums toj; start withdp[0] = 1. - For each
x, updatejfromkdown to 0:dp[j] = 2 · dp[j] + (j ≥ x ? dp[j - x] : 0), modulo10^9 + 7. - 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
kcan never be in T but still double every count. dp[0]keeps doubling (it counts pairs with empty T) — do not skipj = 0.- Reduce modulo
10^9 + 7at every step;2 · dp[j] + dp[j - x]stays below2^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