3082. Find the Sum of the Power of All Subsequences LeetCode Solution
In this guide, you will get 3082. Find the Sum of the Power of All Subsequences LeetCode Solution with the best time and space complexity. The solution to Find the Sum of the Power of All Subsequences problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find the Sum of the Power of All Subsequences
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] 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].
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] <= 104
1 <= k <= 100
Complexity Analysis
Time Complexity: O(nk)
Space Complexity: O(nk)
3082. Find the Sum of the Power of All Subsequences LeetCode Solution in C++
class Solution {
public:
int sumOfPower(vector<int>& nums, int k) {
vector<vector<int>> mem(nums.size(), vector<int>(k + 1, -1));
return sumOfPower(nums, 0, k, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of subsequences in nums[i..n) that sums to j.
int sumOfPower(const vector<int>& nums, int i, int j,
vector<vector<int>>& mem) {
if (j == 0)
// For each of the remaining number, we can either pick it or skip it.
return modPow(2, nums.size() - i);
if (i == nums.size() || j < 0)
return 0;
if (mem[i][j] != -1)
return mem[i][j];
// 1. Include nums[i] in the subsequence and pick it.
// 2. Include nums[i] in the subsequence and skip it.
// 3. Exclude nums[i] in the subsequence.
return mem[i][j] = (sumOfPower(nums, i + 1, j - nums[i], mem) +
L * sumOfPower(nums, i + 1, j, mem)) %
kMod;
}
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
3082. Find the Sum of the Power of All Subsequences LeetCode Solution in Java
class Solution {
public int sumOfPower(int[] nums, int k) {
Integer[][] mem = new Integer[nums.length][k + 1];
return sumOfPower(nums, 0, k, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the number of subsequences in nums[i..n) that sums to j.
private int sumOfPower(int[] nums, int i, int j, Integer[][] mem) {
if (j == 0)
// For each of the remaining number, we can either pick it or skip it.
return (int) modPow(2, nums.length - i);
if (i == nums.length || j < 0)
return 0;
if (mem[i][j] != null)
return mem[i][j];
// 1. Include nums[i] in the subsequence and pick it.
// 2. Include nums[i] in the subsequence and skip it.
// 3. Exclude nums[i] in the subsequence.
return mem[i][j] = (int) ((sumOfPower(nums, i + 1, j - nums[i], mem) + //
L * sumOfPower(nums, i + 1, j, mem)) %
kMod);
}
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
} // code provided by PROGIEZ
3082. Find the Sum of the Power of All Subsequences LeetCode Solution in Python
class Solution:
def sumOfPower(self, nums: list[int], k: int) -> int:
kMod = 1_000_000_007
@functools.lru_cache(None)
def dp(i: int, j: int) -> int:
"""Returns the number of subsequences in nums[i..n) that sums to j."""
if j == 0:
# For each of the remaining number, we can either pick it or skip it.
return pow(2, len(nums) - i, kMod)
if i == len(nums) or j < 0:
return 0
# 1. Include nums[i] in the subsequence and pick it.
# 2. Include nums[i] in the subsequence and skip it.
# 3. Exclude nums[i] in the subsequence.
return (dp(i + 1, j - nums[i]) + 2 * dp(i + 1, j)) % kMod
return dp(0, k) # code by PROGIEZ
