3082. Find the Sum of the Power of All Subsequences Hard

1/**
2 * [3082] Find the Sum of the Power of All Subsequences
3 *
4 * You are given an integer array nums of length n and a positive integer k.
5 * The power of an array of integers is defined as the number of <span data-keyword="subsequence-array">subsequences</span> with their sum equal to k.
6 * Return the sum of power of all subsequences of nums.
7 * Since the answer may be very large, return it modulo 10^9 + 7.
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
11 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> nums = [1,2,3], k = 3 </span>
12 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 6 </span>
13 * Explanation:
14 * There are 5 subsequences of nums with non-zero power:
15 * 
16 * 	The subsequence [<u>1</u>,<u>2</u>,<u>3</u>] has 2 subsequences with sum == 3: [1,2,<u>3</u>] and [<u>1</u>,<u>2</u>,3].
17 * 	The subsequence [<u>1</u>,2,<u>3</u>] has 1 subsequence with sum == 3: [1,2,<u>3</u>].
18 * 	The subsequence [1,<u>2</u>,<u>3</u>] has 1 subsequence with sum == 3: [1,2,<u>3</u>].
19 * 	The subsequence [<u>1</u>,<u>2</u>,3] has 1 subsequence with sum == 3: [<u>1</u>,<u>2</u>,3].
20 * 	The subsequence [1,2,<u>3</u>] has 1 subsequence with sum == 3: [1,2,<u>3</u>].
21 * 
22 * Hence the answer is 2 + 1 + 1 + 1 + 1 = 6.
23 * </div>
24 * <strong class="example">Example 2:
25 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
26 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> nums = [2,3,3], k = 5 </span>
27 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 4 </span>
28 * Explanation:
29 * There are 3 subsequences of nums with non-zero power:
30 * 
31 * 	The subsequence [<u>2</u>,<u>3</u>,<u>3</u>] has 2 subsequences with sum == 5: [<u>2</u>,3,<u>3</u>] and [<u>2</u>,<u>3</u>,3].
32 * 	The subsequence [<u>2</u>,3,<u>3</u>] has 1 subsequence with sum == 5: [<u>2</u>,3,<u>3</u>].
33 * 	The subsequence [<u>2</u>,<u>3</u>,3] has 1 subsequence with sum == 5: [<u>2</u>,<u>3</u>,3].
34 * 
35 * Hence the answer is 2 + 1 + 1 = 4.
36 * </div>
37 * <strong class="example">Example 3:
38 * <div class="example-block" style="border-color: var(--border-tertiary); border-left-width: 2px; color: var(--text-secondary); font-size: .875rem; margin-bottom: 1rem; margin-top: 1rem; overflow: visible; padding-left: 1rem;">
39 * Input:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> nums = [1,2,3], k = 7 </span>
40 * Output:  <span class="example-io" style="font-family: Menlo,sans-serif; font-size: 0.85rem;"> 0 </span>
41 * Explanation: There exists no subsequence with sum 7. Hence all subsequences of nums have power = 0.
42 * </div>
43 *  
44 * Constraints:
45 * 
46 * 	1 <= n <= 100
47 * 	1 <= nums[i] <= 10^4
48 * 	1 <= k <= 100
49 * 
50 */
51pub struct Solution {}
52
53// problem: https://leetcode.com/problems/find-the-sum-of-the-power-of-all-subsequences/
54// discuss: https://leetcode.com/problems/find-the-sum-of-the-power-of-all-subsequences/discuss/?currentPage=1&orderBy=most_votes&query=
55
56// submission codes start here
57
58impl Solution {
59    pub fn sum_of_power(nums: Vec<i32>, k: i32) -> i32 {
60        0
61    }
62}
63
64// submission codes end
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_3082() {
72    }
73}
74