3082. Find the Sum of the Power of All Subsequences

Description

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.

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] has 2 subsequences with sum == 3: [1,2,3] and [1,2,3].
The subsequence [1,2,3] has 1 subsequence with sum == 3: [1,2,3].
The subsequence [1,2,3] has 1 subsequence with sum == 3: [1,2,3].
The subsequence [1,2,3] has 1 subsequence with sum == 3: [1,2,3].
The subsequence [1,2,3] has 1 subsequence with sum == 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 with sum == 5: [2,3,3] and [2,3,3].
The subsequence [2,3,3] has 1 subsequence with sum == 5: [2,3,3].
The subsequence [2,3,3] has 1 subsequence with sum == 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 <= 100
1 <= nums[i] <= 10⁴
1 <= k <= 100

Solutions

Solution 1: Dynamic Programming

Thinking

For every subsequence \(S\) we count subsequences of \(S\) whose sum is \(k\), then sum those counts. \(n,k \le 100\).

An element may be outside \(S\), in \(S\) but not in the summing subsequence \(T\), or in \(T\). The first two share the same sum and both copy the previous state.

Hence \(f[i][j]=2f[i-1][j]+f[i-1][j-x]\) with \(f[0][0]=1\).

The problem requires us to find all subsequences \(\textit{S}\) in the given array \(\textit{nums}\), and then calculate the number of ways for each subsequence \(\textit{T}\) such that the sum of \(\textit{T}\) equals \(\textit{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 \(\textit{S}\), in which case \(f[i][j] = f[i-1][j]\);
In the subsequence \(\textit{S}\), but not in the subsequence \(\textit{T}\), in which case \(f[i][j] = f[i-1][j]\);
In the subsequence \(\textit{S}\), and in the subsequence \(\textit{T}\), in which case \(f[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 \(\textit{nums}\), and \(k\) is the given positive integer.

Python3JavaC++GoTypeScript

class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        mod = 10**9 + 7
        n = len(nums)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 1
        for i, x in enumerate(nums, 1):
            for j in range(k + 1):
                f[i][j] = f[i - 1][j] * 2 % mod
                if j >= x:
                    f[i][j] = (f[i][j] + f[i - 1][j - x]) % mod
        return f[n][k]

class Solution {
    public int sumOfPower(int[] nums, int k) {
        final int mod = (int) 1e9 + 7;
        int n = nums.length;
        int[][] f = new int[n + 1][k + 1];
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int 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];
    }
}

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int mod = 1e9 + 7;
        int n = nums.size();
        int f[n + 1][k + 1];
        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int 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]
}

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];
}

Solution 2: Dynamic Programming (Optimization)

Thinking

Part I’s transition only reads the previous row at \(j\) and \(j-x\), so the first dimension can go.

Updating a one-dimensional array from the back avoids reusing a newly written \(j-x\) and drops extra space to \(O(k)\).

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 \(\textit{nums}\), and \(k\) is the given positive integer.

Python3JavaC++GoTypeScript

class Solution:
    def sumOfPower(self, nums: List[int], k: int) -> int:
        mod = 10**9 + 7
        f = [1] + [0] * k
        for x in nums:
            for j in range(k, -1, -1):
                f[j] = (f[j] * 2 + (0 if j < x else f[j - x])) % mod
        return f[k]

class Solution {
    public int sumOfPower(int[] nums, int k) {
        final int mod = (int) 1e9 + 7;
        int[] f = new int[k + 1];
        f[0] = 1;
        for (int x : nums) {
            for (int j = k; j >= 0; --j) {
                f[j] = (f[j] * 2 % mod + (j >= x ? f[j - x] : 0)) % mod;
            }
        }
        return f[k];
    }
}

class Solution {
public:
    int sumOfPower(vector<int>& nums, int k) {
        const int mod = 1e9 + 7;
        int f[k + 1];
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for (int x : nums) {
            for (int j = k; j >= 0; --j) {
                f[j] = (f[j] * 2 % mod + (j >= x ? f[j - x] : 0)) % 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]
}

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];
}

3082. Find the Sum of the Power of All Subsequences

Description

Solutions

Solution 1: Dynamic Programming

Solution 2: Dynamic Programming (Optimization)

Comments