Find the sum of the power of all subsequences

Array Dynamic Programming

38.1% acceptance

Feb 25, 2026

168

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^9 + 7.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_of_power(nums: Vec<i32>, k: i32) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let n = nums.len();
    let k = k as usize;
    // Answer = sum over subsets T with sum(T)=k of 2^(n-|T|)
    // dp[j] = sum over subsets T of processed elements with sum j of (1/2)^|T|
    // Answer = 2^n * dp[k]
    // inv2 = modular inverse of 2
    let inv2 = (MOD + 1) / 2; // since MOD is odd, (MOD+1)/2 = inverse of 2
    let mut dp = vec![0i64; k + 1];
    dp[0] = 1;
    for &x in &nums {
      let x = x as usize;
      let mut new_dp = dp.clone();
      for j in x..=k {
        new_dp[j] = (new_dp[j] + dp[j - x] % MOD * inv2) % MOD;
      }
      dp = new_dp;
    }
    let pow2n = (0..n).fold(1i64, |acc, _| acc * 2 % MOD);
    ((dp[k] * pow2n) % MOD) as i32
  }
}