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 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]
has2
subsequences withsum == 3
:[1,2,3]
and[1,2,3]
. - The subsequence
[1,2,3]
has1
subsequence withsum == 3
:[1,2,3]
. - The subsequence
[1,2,3]
has1
subsequence withsum == 3
:[1,2,3]
. - The subsequence
[1,2,3]
has1
subsequence withsum == 3
:[1,2,3]
. - The subsequence
[1,2,3]
has1
subsequence 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 <= 100
1 <= nums[i] <= 104
1 <= k <= 100
Solutions
Solution 1: Dynamic Programming
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.
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
Solution 2: 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 $\textit{nums}$, and $k$ is the given positive integer.
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|