Find the Sum of the Power of All Subsequences

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

Understanding the Visualization

Input

Array [1,2,1] with target sum k=2

Process

For each subsequence, count ways to sum to k

Output

Sum all powers: 6

Key Takeaway

🎯 Key Insight: Each element can contribute to current subsequence or be saved for future ones, leading to exponential state space

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

Approach	Time	Space	Notes
✓ Dynamic Programming with States	O(n × sum × 2^n)	O(n × sum × 2^n)	Track elements chosen, elements available, and current sum using DP
Brute Force - Generate All Subsequences	O(4^n)	O(n)	Generate all 2^n subsequences and count target sums for each
Memoization Approach	O(3^n)	O(3^n)	Use recursion with memoization to avoid recalculating same states

Dynamic Programming with States — Algorithm Steps

Define DP state as (index, sum, remaining_count)
For each element, choose to include in current subsequence or keep available
When sum equals k, multiply by 2^remaining_count

Visualization

Tap to expand

Step-by-Step Walkthrough

State Definition

(index, current_sum, remaining_elements_mask)

Transitions

Include element or keep it for future use

Power Calculation

When sum=k, multiply by 2^remaining

Code -

solution.c — C

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

#define MOD 1000000007
#define MAX_STATES 100000

typedef struct {
    int idx, currSum, remainingMask;
    long long result;
} DPEntry;

DPEntry dpTable[MAX_STATES];
int dpSize = 0;

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = (result * base) % mod;
        }
        exp = exp / 2;
        base = (base * base) % mod;
    }
    return result;
}

int countBits(int mask) {
    int count = 0;
    while (mask) {
        count += mask & 1;
        mask >>= 1;
    }
    return count;
}

long long findDP(int idx, int currSum, int remainingMask) {
    for (int i = 0; i < dpSize; i++) {
        if (dpTable[i].idx == idx && dpTable[i].currSum == currSum && dpTable[i].remainingMask == remainingMask) {
            return dpTable[i].result;
        }
    }
    return -1;
}

void addDP(int idx, int currSum, int remainingMask, long long result) {
    if (dpSize < MAX_STATES) {
        dpTable[dpSize].idx = idx;
        dpTable[dpSize].currSum = currSum;
        dpTable[dpSize].remainingMask = remainingMask;
        dpTable[dpSize].result = result;
        dpSize++;
    }
}

long long solve(int idx, int currSum, int remainingMask, int* nums, int numsSize, int k) {
    if (idx == numsSize) {
        if (currSum == k) {
            return modPow(2, countBits(remainingMask), MOD);
        }
        return 0;
    }
    
    long long cached = findDP(idx, currSum, remainingMask);
    if (cached != -1) {
        return cached;
    }
    
    // Option 1: Include nums[idx] in current subsequence
    long long result = solve(idx + 1, currSum + nums[idx], remainingMask, nums, numsSize, k);
    
    // Option 2: Keep nums[idx] for future subsequences
    result = (result + solve(idx + 1, currSum, remainingMask | (1 << idx), nums, numsSize, k)) % MOD;
    
    addDP(idx, currSum, remainingMask, result);
    return result;
}

int solution(int* nums, int numsSize, int k) {
    dpSize = 0;
    return solve(0, 0, 0, nums, numsSize, k);
}

int main() {
    int nums[20];
    int numsSize = 0;
    int k;
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    scanf("%d", &k);
    
    int result = solution(nums, numsSize, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × sum × 2^n)

Three dimensions: n positions, sum range, and 2^n possible remaining sets

⚠ Quadratic Growth

Space Complexity

O(n × sum × 2^n)

DP table stores all possible states

⚠ Quadratic 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

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with States — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler