Find the Sum of the Power of All Subsequences solution and explanation
Google
6 more videos on this problem
3082. Find the Sum of the Power of All Subsequences | 0-1 knapsack DP | Binary ExponentiationAryan Mittal · 36:13 · 3K views
3082. Find the Sum of the Power of All Subsequences | Leetcode Biweekly 126codingMohan · 50:23 · 748 views
3082. Find the Sum of the Power of All Subsequences (Leetcode Hard)Programming Live with Larry · 19:32 · 646 views
3082. Find the Sum of the Power of All Subsequences || Biweekly Contest 126 || LeetcodeAshish Kumar · 25:49 · 200 views
LeetCode | 3082. Find the Sum of the Power of All Subsequences | Hard | Biweekly Contest 126Coding with Bobby · 13:49 · 151 views
Leetcode 3082 | Find the Sum of Power of All Subsequences | Biweekly Contest 126Road To FAANG · 13:06 · 55 views
✂️Biweekly Contest 126 is Here ! Problem 4:3082. Find the Sum of the Power of All SubsequencesAchyuth Chowdary · 15:24 · 25 views
The problem
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 power of all subsequences of nums.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: nums = [1,2,3], k = 3
Output: 6
Explanation:
There are 5 subsequences of nums with non-zero power:
- The subsequence
[1,2,3]has2subsequences withsum == 3:[1,2,3]and[1,2,3]. - The subsequence
[1,2,3]has1subsequence withsum == 3:[1,2,3]. - The subsequence
[1,2,3]has1subsequence withsum == 3:[1,2,3]. - The subsequence
[1,2,3]has1subsequence withsum == 3:[1,2,3]. - The subsequence
[1,2,3]has1subsequence withsum == 3:[1,2,3].
Hence the answer is 2 + 1 + 1 + 1 + 1 = 6.
Example 2:
Input: nums = [2,3,3], k = 5
Output: 4
Explanation:
There are 3 subsequences of nums with non-zero power:
- The subsequence
[2,3,3]has 2 subsequences withsum == 5:[2,3,3]and[2,3,3]. - The subsequence
[2,3,3]has 1 subsequence withsum == 5:[2,3,3]. - The subsequence
[2,3,3]has 1 subsequence withsum == 5:[2,3,3].
Hence the answer is 2 + 1 + 1 = 4.
Example 3:
Input: nums = [1,2,3], k = 7
Output: 0
Explanation: There exists no subsequence with sum 7. Hence all subsequences of nums have power = 0.
Constraints:
1 <= n <= 1001 <= nums[i] <= 1041 <= k <= 100
Approach overview
Problem Overview: You are given an integer array and a target value k. For every subsequence whose elements sum to k, its power depends on how many elements are not chosen. The task is to compute the total power contributed by all such subsequences.
Approach 1: Backtracking Enumeration (O(2^n) time, O(n) space)
This approach generates every possible subsequence using recursive backtracking. At each index you decide whether to include the element or skip it. When a subsequence reaches sum k, compute its contribution using the number of unused elements, typically 2^(n - length), and add it to the result. The recursion explores all 2^n combinations, making it impractical for large inputs but useful for understanding the structure of the problem. This brute‑force exploration highlights that the problem is essentially a subset‑sum variant over an array.
Approach 2: Dynamic Programming on Subsequence Sum (O(n · k) time, O(k) or O(n · k) space)
The optimized solution treats the problem as a variation of subset sum using dynamic programming. Instead of enumerating subsequences, maintain a DP state where dp[s] tracks the number of ways to build subsequences with sum s using processed elements. For each value x in the array, iterate sums backward and update dp[s + x]. To compute the total power, also track the subsequence length or account for remaining elements using precomputed powers of two. After processing all numbers, aggregate contributions of all subsequences with sum k, multiplying each count by 2^(n - length). This converts exponential exploration into polynomial computation.
The key insight is that the power of a valid subsequence depends only on how many elements were excluded, not their positions. Dynamic programming efficiently counts subsequences by sum while implicitly representing many combinations at once. This technique frequently appears in subset counting and knapsack‑style problems involving DP over sums.
Recommended for interviews: Start by explaining the backtracking idea to show you understand how subsequences are formed. Then move to the dynamic programming solution that tracks subsequence sums. Interviewers typically expect the DP optimization because it reduces the exponential search to roughly O(n · k) while keeping memory manageable.
Approach 1: Backtracking Approach
This approach generates all possible subsets of the input array and calculates their sums. It counts how many subsets have their sum equal to k. This brute-force approach uses recursion and can be optimized with backtracking techniques to avoid entire paths that cannot lead to a viable solution. Due to its computational intensity, this method may not be suited for larger arrays or k values.
MOD = 1000000007
def subsequences_power_sum(nums, k):
def find_subsequences(index, current_sum):
if current_sum == k:
return 1
if index == len(nums):
return 0
include = find_subsequences(index + 1, current_sum + nums[index])
exclude = find_subsequences(index + 1, current_sum)
return (include + exclude) % MOD
return find_subsequences(0, 0)
nums = [1, 2, 3]
print(subsequences_power_sum(nums, 3))import java.util.*;
class Solution {
private static final int MOD = 1000000007;
public int subsequencesPowerSum(int[] nums, int k) {
return findSubsequences(nums, k, 0, 0);
}
private int findSubsequences(int[] nums, int k, int index, int currentSum) {
if (currentSum == k) {
return 1;
}
if (index == nums.length) {
return 0;
}
int include = findSubsequences(nums, k, index + 1, currentSum + nums[index]);
int exclude = findSubsequences(nums, k, index + 1, currentSum);
return (include + exclude) % MOD;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
int result = sol.subsequencesPowerSum(nums, 3);
System.out.println(result);
}
}#include <iostream>
#include <vector>
#define MOD 1000000007
void findSubsequencesPower(std::vector<int>& nums, int k, int index, int currentSum, int& count) {
if (currentSum == k) {
count = (count + 1) % MOD;
}
if (index == nums.size()) return;
// Include the current index element
findSubsequencesPower(nums, k, index + 1, currentSum + nums[index], count);
// Exclude the current index element
findSubsequencesPower(nums, k, index + 1, currentSum, count);
}
int main() {
std::vector<int> nums = {1, 2, 3};
int k = 3;
int count = 0;
findSubsequencesPower(nums, k, 0, 0, count);
std::cout << count << std::endl;
return 0;
}const MOD = 1000000007;
function subsequencesPowerSum(nums, k) {
function findSubsequences(index, currentSum) {
if (currentSum === k) {
return 1;
}
if (index === nums.length) {
return 0;
}
let include = findSubsequences(index + 1, currentSum + nums[index]);
let exclude = findSubsequences(index + 1, currentSum);
return (include + exclude) % MOD;
}
return findSubsequences(0, 0);
}
const nums = [1, 2, 3];
console.log(subsequencesPowerSum(nums, 3));#include <stdio.h>
#define MOD 1000000007
void generateSubsequences(int *nums, int n, int k, int index, int currentSum, int *count) {
if (currentSum == k) {
(*count)++;
*count %= MOD;
}
if (index == n) return;
// Include nums[index] in subsequence
generateSubsequences(nums, n, k, index + 1, currentSum + nums[index], count);
// Exclude nums[index] from subsequence
generateSubsequences(nums, n, k, index + 1, currentSum, count);
}
int main() {
int nums[] = {1, 2, 3};
int k = 3;
int count = 0;
generateSubsequences(nums, 3, k, 0, 0, &count);
printf("%d\n", count);
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
public int SubsequencePowerSum(int[] nums, int k) {
return FindSubsequences(nums, k, 0, 0);
}
private int FindSubsequences(int[] nums, int k, int index, int currentSum) {
if (currentSum == k) {
return 1;
}
if (index == nums.Length) {
return 0;
}
int include = FindSubsequences(nums, k, index + 1, currentSum + nums[index]);
int exclude = FindSubsequences(nums, k, index + 1, currentSum);
return (include + exclude) % MOD;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
Console.WriteLine(solution.SubsequencePowerSum(nums, 3));
}
}Python implementation employs a helper function 'find_subsequences' to recursively process elements. Using Python's natural handling of integers allows functional decompositions that work identically to previous examples. As recursion progresses, counts of subsequences achieving sum k aggregate over calls.
Time Complexity: O(2^n), where n is the length of nums array.
Space Complexity: O(n) - maximum recursion stack depth.
Approach 2: Dynamic Programming Approach
This optimized approach leverages dynamic programming to resolve the problem more efficiently. It uses a DP table where dp[i][j] indicates the number of subsequences using the first i elements of nums with a sum of j. The transition is characterized by using or skipping the current element to reach different state sums. The solution exploits the reduced range from constraint k ≤ 100 to use space effectively.
MOD = 1000000007
def subsequences_power_sum(nums, k):
dp = [0] * (k + 1)
dp[0] = 1 # One way to make sum 0
for num in nums:
for j in range(k, num - 1, -1):
dp[j] = (dp[j] + dp[j - num]) % MOD
return dp[k]
nums = [1, 2, 3]
print(subsequences_power_sum(nums, 3))import java.util.*;
class Solution {
private static final int MOD = 1000000007;
public int subsequencesPowerSum(int[] nums, int k) {
int[] dp = new int[k + 1];
dp[0] = 1; // Only one way to get sum = 0
for (int num : nums) {
for (int j = k; j >= num; j--) {
dp[j] = (dp[j] + dp[j - num]) % MOD;
}
}
return dp[k];
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
System.out.println(solution.subsequencesPowerSum(nums, 3));
}
}#include <iostream>
#include <vector>
#include <cstring>
#define MOD 1000000007
int subsequencePowerSum(std::vector<int>& nums, int k) {
std::vector<int> dp(k + 1, 0);
dp[0] = 1; // One way to have sum = 0
for (int num : nums) {
for (int j = k; j >= num; j--) {
dp[j] = (dp[j] + dp[j - num]) % MOD;
}
}
return dp[k];
}
int main() {
std::vector<int> nums = {1, 2, 3};
int result = subsequencePowerSum(nums, 3);
std::cout << result << std::endl;
return 0;
}const MOD = 1000000007;
function subsequencesPowerSum(nums, k) {
let dp = new Array(k + 1).fill(0);
dp[0] = 1; // base case: one way to sum to zero
nums.forEach(num => {
for (let j = k; j >= num; j--) {
dp[j] = (dp[j] + dp[j - num]) % MOD;
}
});
return dp[k];
}
const nums = [1, 2, 3];
console.log(subsequencesPowerSum(nums, 3));#include <stdio.h>
#include <string.h>
#define MOD 1000000007
int powerOfSubsequences(int *nums, int n, int k) {
int dp[k + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1; // Base case: single subset with zero sum
for (int i = 0; i < n; i++) {
for (int j = k; j >= nums[i]; j--) {
dp[j] = (dp[j] + dp[j - nums[i]]) % MOD;
}
}
return dp[k];
}
int main() {
int nums[] = {1, 2, 3};
int k = 3;
printf("%d\n", powerOfSubsequences(nums, 3, k));
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
public int SubsequencePowerSum(int[] nums, int k) {
int[] dp = new int[k + 1];
dp[0] = 1; // Only way to get sum 0
foreach (int num in nums) {
for (int j = k; j >= num; j--) {
dp[j] = (dp[j] + dp[j - num]) % MOD;
}
}
return dp[k];
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] nums = {1, 2, 3};
Console.WriteLine(solution.SubsequencePowerSum(nums, 3));
}
}Python's dynamic programming tact encapsulates a table update schema, iterating inner loops inversely for numeration control. This structured modification records evolving potential derivations matching prior outcomes, modulating fastidious tracking.
Time Complexity: O(n * k), each loop interacts over length and possible sums;
Space Complexity: O(k), minimal due to succinct record inclusion scheme.
Approach 3: Dynamic Programming
The problem requires us to find all subsequences S in the given array nums, and then calculate the number of ways for each subsequence T such that the sum of T equals k.
We define f[i][j] to represent the number of ways to form subsequences with the first i numbers such that the sum of each subsequence equals j. Initially, f[0][0] = 1, and all other positions are 0.
For the i-th number x, there are three cases:
- Not in the subsequence
S, in which casef[i][j] = f[i-1][j]; - In the subsequence
S, but not in the subsequenceT, in which casef[i][j] = f[i-1][j]; - In the subsequence
S, and in the subsequenceT, in which casef[i][j] = f[i-1][j-x].
In summary, the state transition equation is:
$
f[i][j] = f[i-1][j] times 2 + f[i-1][j-x]
The final answer is f[n][k].
The time complexity is O(n times k), and the space complexity is O(n times k). Here, n is the length of the array nums, and k$ is the given positive integer.
function sumOfPower(nums: number[], k: number): number {
const mod = 10 ** 9 + 7;
const n = nums.length;
const f: number[][] = Array.from({ length: n + 1 }, () => Array(k + 1).fill(0));
f[0][0] = 1;
for (let i = 1; i <= n; ++i) {
for (let j = 0; j <= k; ++j) {
f[i][j] = (f[i - 1][j] * 2) % mod;
if (j >= nums[i - 1]) {
f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod;
}
}
}
return f[n][k];
}func sumOfPower(nums []int, k int) int {
const mod int = 1e9 + 7
n := len(nums)
f := make([][]int, n+1)
for i := range f {
f[i] = make([]int, k+1)
}
f[0][0] = 1
for i := 1; i <= n; i++ {
for j := 0; j <= k; j++ {
f[i][j] = (f[i-1][j] * 2) % mod
if j >= nums[i-1] {
f[i][j] = (f[i][j] + f[i-1][j-nums[i-1]]) % mod
}
}
}
return f[n][k]
}Approach 4: Dynamic Programming (Optimization)
In the state transition equation from Solution 1, the value of f[i][j] only depends on f[i-1][j] and f[i-1][j-x]. Therefore, we can optimize the first dimension of the space, reducing the space complexity to O(k).
Time complexity is O(n times k), and space complexity is O(k). Here, n is the length of the array nums, and k is the given positive integer.
function sumOfPower(nums: number[], k: number): number {
const mod = 10 ** 9 + 7;
const f: number[] = Array(k + 1).fill(0);
f[0] = 1;
for (const x of nums) {
for (let j = k; ~j; --j) {
f[j] = (f[j] * 2) % mod;
if (j >= x) {
f[j] = (f[j] + f[j - x]) % mod;
}
}
}
return f[k];
}func sumOfPower(nums []int, k int) int {
const mod int = 1e9 + 7
f := make([]int, k+1)
f[0] = 1
for _, x := range nums {
for j := k; j >= 0; j-- {
f[j] = f[j] * 2 % mod
if j >= x {
f[j] = (f[j] + f[j-x]) % mod
}
}
}
return f[k]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Backtracking Approach | Time Complexity: O(2^n), where n is the length of nums array. |
| Dynamic Programming Approach | Time Complexity: O(n * k), each loop interacts over length and possible sums; |
| Dynamic Programming | – |
| Dynamic Programming (Optimization) | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Backtracking Enumeration | O(2^n) | O(n) | Small input sizes or when demonstrating the brute-force subsequence generation logic |
| Dynamic Programming (Sum + Length Tracking) | O(n · k) | O(n · k) | General optimized solution when subsequence sums must be counted precisely |
| Space Optimized DP | O(n · k) | O(k) | Preferred in interviews when memory usage matters and DP transitions allow rolling arrays |
Frequently asked questions
Is Find the Sum of the Power of All Subsequences easy or hard?
Find the Sum of the Power of All Subsequences is classified as a Hard problem. It requires understanding subsequence enumeration, combinatorial counting, and dynamic programming optimization. Many candidates initially attempt brute force before recognizing the subset-sum DP pattern.
Find the Sum of the Power of All Subsequences Python/Java solution
Python and Java implementations typically use dynamic programming with a 1D or 2D DP array for subset sums. Each element updates the DP states in reverse order to avoid reuse within the same iteration. The final answer aggregates contributions for subsequences whose sum equals k.
How to solve Find the Sum of the Power of All Subsequences in O(n · k)?
Use dynamic programming similar to subset sum. Maintain a DP array where dp[s] counts subsequences with sum s while iterating through the array. For each number update sums in reverse order, and accumulate the contribution of subsequences that reach k using powers of two based on remaining elements.
What is the best approach for Find the Sum of the Power of All Subsequences?
The most efficient approach uses dynamic programming over subsequence sums. Track how many subsequences produce each sum while iterating through the array, then compute the power contribution for subsequences that reach sum k. This reduces the exponential subsequence search to roughly O(n · k) time.
Is Find the Sum of the Power of All Subsequences asked at Google/Amazon/Meta?
Problems involving subsequence counting, subset sums, and dynamic programming frequently appear in interviews at companies like Google, Amazon, and Meta. This problem combines subset enumeration with combinatorial counting, which is a common advanced DP interview pattern.
What data structure is used in Find the Sum of the Power of All Subsequences?
The core data structure is a dynamic programming array or table indexed by possible sums. It stores counts of subsequences reaching each sum while processing the array. Precomputed power-of-two arrays are often used to quickly calculate contribution weights.
What is the time complexity of Find the Sum of the Power of All Subsequences?
The brute force backtracking solution runs in O(2^n) time because every subsequence must be generated. The optimized dynamic programming approach runs in O(n · k) time, where n is the array length and k is the target sum. Space complexity ranges from O(k) to O(n · k) depending on the DP design.