2518. Number of Great Partitions Hard

1/**
2 * [2518] Number of Great Partitions
3 *
4 * You are given an array nums consisting of positive integers and an integer k.
5 * Partition the array into two ordered groups such that each element is in exactly one group. A partition is called great if the sum of elements of each group is greater than or equal to k.
6 * Return the number of distinct great partitions. Since the answer may be too large, return it modulo 10^9 + 7.
7 * Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.
8 *  
9 * <strong class="example">Example 1:
10 * 
11 * Input: nums = [1,2,3,4], k = 4
12 * Output: 6
13 * Explanation: The great partitions are: ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) and ([4], [1,2,3]).
14 * 
15 * <strong class="example">Example 2:
16 * 
17 * Input: nums = [3,3,3], k = 4
18 * Output: 0
19 * Explanation: There are no great partitions for this array.
20 * 
21 * <strong class="example">Example 3:
22 * 
23 * Input: nums = [6,6], k = 2
24 * Output: 2
25 * Explanation: We can either put nums[0] in the first partition or in the second partition.
26 * The great partitions will be ([6], [6]) and ([6], [6]).
27 * 
28 *  
29 * Constraints:
30 * 
31 * 	1 <= nums.length, k <= 1000
32 * 	1 <= nums[i] <= 10^9
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/number-of-great-partitions/
38// discuss: https://leetcode.com/problems/number-of-great-partitions/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41
42impl Solution {
43    pub fn count_partitions(nums: Vec<i32>, k: i32) -> i32 {
44        0
45    }
46}
47
48// submission codes end
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53
54    #[test]
55    fn test_2518() {
56    }
57}
58