2518. Number of Great Partitions

/*
You are given an array nums consisting of positive integers and an integer k.

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.

Return the number of distinct great partitions. Since the answer may be too large, return it modulo 109 + 7.

Two partitions are considered distinct if some element nums[i] is in different groups in the two partitions.



Example 1:

Input: nums = [1,2,3,4], k = 4
Output: 6
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]).
Example 2:

Input: nums = [3,3,3], k = 4
Output: 0
Explanation: There are no great partitions for this array.
Example 3:

Input: nums = [6,6], k = 2
Output: 2
Explanation: We can either put nums[0] in the first partition or in the second partition.
The great partitions will be ([6], [6]) and ([6], [6]).


Constraints:

1 <= nums.length, k <= 1000
1 <= nums[i] <= 10^9

link- https://leetcode.com/problems/number-of-great-partitions/

*/

class Solution {
public:
    long long int dp[1001][1001];

    long long int binaryExponentiation(long long int base, int power){
        long long int res=1;
        while(power>0){
            if(power%2==0){
                base=(base*base)%1000000007;
                power/=2;
            }
            else{
                res=(res*base)%1000000007;
                power--;
            }
        }
        return res;
    }

    long long int helper(vector<int> &nums, int curr, int k){
        if(curr==nums.size()){
            return 1;
        }
        if(dp[curr][k]!=-1){
            return dp[curr][k];
        }
        long long int res=0;
        if(k-nums[curr]>=0){
            res=(res+helper(nums,curr+1,k-nums[curr]))%1000000007;
        }
        res=(res+helper(nums,curr+1,k))%1000000007;
        return dp[curr][k]=res;
    }

    int countPartitions(vector<int>& nums, int k) {
        // there are 2^n possible partitions, including empty subsequences
        memset(dp,-1,sizeof(dp));
        long long int sum=accumulate(nums.begin(),nums.end(),0LL);
        if(2*k>sum){
            return 0;
        }
        int n=nums.size();
        long long int total=(binaryExponentiation(2,n))%1000000007;
        long long int invalids=(helper(nums,0,k-1)*2)%1000000007; // empty subseq included
        return (total-invalids+1000000007)%1000000007;
    }
};



/*
Explanation-

1) Find total partitions
2) Remove out the bad partitions, i.e atleast one group/subset less than k
3) Subtract total-bad and return

TC- O(nk)

Find all subsets of [1,2,3,4]
That is 16 of them, according to formula 2^n.

[1] [2, 3, 4]
[2] [1, 3, 4]
[3] [1, 2, 4]
[4] [1, 2, 3]
[1, 2] [3, 4]
[1, 3] [2, 4]
[1, 4] [2, 3]
[2, 3] [1, 4]
[2, 4] [1, 3]
[3, 4] [1, 2]
[1, 2, 3] [4]
[1, 2, 4] [3]
[1, 3, 4] [2]
[2, 3, 4] [1]
[1,2.3,4] []
[] [1,2,3,4]

Now, you remove all the subsets having less than k=3 sum. that is

[1, 2, 3, 4] []
[1] [2, 3, 4]
[2] [1, 3, 4]
[3] [1, 2, 4]
[1, 2] [3, 4]

[] [1, 2, 3, 4]
[2, 3, 4] [1]
[1, 3, 4] [2]
[1, 2, 4] [3]
[3, 4] [1, 2]


Now you can clearly see there are 8, but your function will return 4 but multiply 2 to it since you can clearly see the other 2 are mirror image of one another.

Now great partition=total-bad partition.
*/