Find the Sum of the Power of All Subsequences - 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 10⁹ + 7.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1], k = 2

› Output: 6

💡 Note: Subsequences and their powers: [] has 0 ways, [1] has 0 ways, [2] has 1 way (itself), [1] has 0 ways, [1,2] has 1 way ([2]), [1,1] has 1 way ([1,1]), [2,1] has 1 way ([2]), [1,2,1] has 2 ways ([2] and [1,1]). Total: 0+0+1+0+1+1+1+2 = 6

Example 2 — Single Element

$ Input: nums = [1], k = 1

› Output: 1

💡 Note: Only one subsequence [1] which has 1 way to sum to k=1 (the element itself). Total power: 1

Example 3 — No Valid Sums

$ Input: nums = [2,3], k = 1

› Output: 0

💡 Note: Subsequences: [] (0 ways), [2] (0 ways), [3] (0 ways), [2,3] (0 ways). No subsequence can sum to k=1. Total: 0

Constraints

1 ≤ nums.length ≤ 100
1 ≤ nums[i] ≤ 100
1 ≤ k ≤ 100

Visualization

Tap to expand

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is that each element can either be included in the current subsequence or kept available for future subsequences. We use dynamic programming with memoization to track states (index, sum, remaining_elements) and calculate the power by multiplying 2^remaining_count when sum equals k. Best approach uses DP with time O(3^n) and space O(3^n).

Common Approaches

✓ Brute Force - Generate All Subsequences

⏱️ Time: O(4^n) Space: O(n)

For each subsequence, count how many of its sub-subsequences sum to k. This requires generating all possible subsequences (2^n) and for each one, checking all its sub-subsequences.

Dynamic Programming with States

⏱️ Time: O(n × sum × 2^n) Space: O(n × sum × 2^n)

We use dynamic programming where each state represents (index, current_sum, remaining_elements). For each position, we can either include the element in our current subsequence or save it for later subsequences.

Memoization Approach

⏱️ Time: O(3^n) Space: O(3^n)

Instead of generating all subsequences explicitly, we use recursion to explore include/exclude decisions for each element, while memoizing results to avoid redundant calculations.

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all 2^n subsequences using bit manipulation
For each subsequence, count sub-subsequences that sum to k
Sum all counts and return modulo 10^9+7

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsequences

Create all 2^n possible subsequences

Count Target Sums

For each subsequence, count sub-subsequences summing to k

Sum Powers

Add all counts together

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007

int countSubsequencesWithSum(int* arr, int size, int target) {
    if (size == 0) {
        return target == 0 ? 1 : 0;
    }
    
    int count = 0;
    
    // Generate all subsequences of arr
    for (int mask = 0; mask < (1 << size); mask++) {
        int currSum = 0;
        for (int i = 0; i < size; i++) {
            if (mask & (1 << i)) {
                currSum += arr[i];
            }
        }
        if (currSum == target) {
            count++;
        }
    }
    
    return count;
}

int solution(int* nums, int numsSize, int k) {
    long long totalPower = 0;
    
    // Generate all 2^n subsequences
    for (int mask = 0; mask < (1 << numsSize); mask++) {
        int subseq[20];
        int subseqSize = 0;
        
        for (int i = 0; i < numsSize; i++) {
            if (mask & (1 << i)) {
                subseq[subseqSize++] = nums[i];
            }
        }
        
        // Count subsequences of subseq that sum to k
        int power = countSubsequencesWithSum(subseq, subseqSize, k);
        totalPower = (totalPower + power) % MOD;
    }
    
    return totalPower;
}

int main() {
    char line[1000];
    int nums[100];
    int numsSize = 0;
    
    if (fgets(line, sizeof(line), stdin)) {
        char *ptr = line;
        // Skip '['
        while (*ptr && *ptr != '[') ptr++;
        if (*ptr == '[') ptr++;
        
        // Parse numbers
        while (*ptr && *ptr != ']') {
            while (*ptr && (*ptr == ' ' || *ptr == ',')) ptr++;
            if (*ptr && *ptr != ']') {
                nums[numsSize++] = atoi(ptr);
                while (*ptr && *ptr != ',' && *ptr != ']') ptr++;
            }
        }
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^n)

2^n subsequences, each requiring 2^m checks where m is subsequence length

✓ Linear Growth

Space Complexity

O(n)

Recursion stack depth and temporary storage

⚡ Linearithmic Space

8.9K Views

Medium Frequency

~45 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Find the Sum of the Power of All Subsequences - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler