# Number of Great Partitions
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-great-partitions)
Canonical: https://scaleengineer.com/dsa/problems/number-of-great-partitions
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Darwinbox](https://scaleengineer.com/companies/darwinbox)
---
## Problem
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] <= 109`

# Approaches
## Brute-Force Recursive Approach
This is a straightforward approach that directly models the problem statement. It explores every possible way to partition the array `nums` into two groups by making a binary choice for each element. For each complete partition, it checks if it satisfies the 'great' condition (both group sums are at least `k`).
**Time:** O(2^n)
For each of the `n` elements, the function branches into two recursive calls. This creates a recursion tree with `2^n` leaf nodes, leading to an exponential runtime. · **Space:** O(n)
This is the space required for the recursion stack, where `n` is the number of elements in `nums`.
**Pros:** Simple to understand and implement.; Directly translates the problem definition into code.
**Cons:** Extremely inefficient and will lead to a 'Time Limit Exceeded' (TLE) verdict for the given constraints.; The number of states to explore grows exponentially with the input size `n`.
### Explanation
The method uses a recursive function to generate all `2^n` possible partitions. The state of the recursion is defined by the current index of the element being placed and the running sums of the two groups.

```java
class Solution {
    private int k;
    private int[] nums;
    private int n;
    private int MOD = 1_000_000_007;

    public int countPartitions(int[] nums, int k) {
        this.nums = nums;
        this.k = k;
        this.n = nums.length;
        // Note: This will time out on larger inputs but illustrates the concept.
        return solve(0, 0, 0);
    }

    private int solve(int index, long sum1, long sum2) {
        // Base case: all elements have been partitioned
        if (index == n) {
            if (sum1 >= k && sum2 >= k) {
                return 1;
            }
            return 0;
        }

        // Recursive step: explore two choices for the current element
        
        // Choice 1: Add nums[index] to group 1
        int count1 = solve(index + 1, sum1 + nums[index], sum2);

        // Choice 2: Add nums[index] to group 2
        int count2 = solve(index + 1, sum1, sum2 + nums[index]);

        return (count1 + count2) % MOD;
    }
}
```
Memoization is not feasible for this approach because the `sum1` and `sum2` can become very large, leading to an unmanageably large state space for the memoization table.
### Algorithm
- Define a recursive function, say `solve(index, sum1, sum2)`, where `index` is the current element being considered, and `sum1`, `sum2` are the current sums of the two groups.
- **Base Case:** If `index` equals the length of the `nums` array, all elements have been partitioned. Check if `sum1 >= k` and `sum2 >= k`. If both conditions are met, we have found one great partition, so return 1. Otherwise, return 0.
- **Recursive Step:** For the element `nums[index]`, explore two possibilities:
  1. Add `nums[index]` to the first group: Make a recursive call `solve(index + 1, sum1 + nums[index], sum2)`.
  2. Add `nums[index]` to the second group: Make a recursive call `solve(index + 1, sum1, sum2 + nums[index])`.
- The result for the current state is the sum of the results from these two recursive calls, taken modulo `10^9 + 7`.
- The initial call to start the process is `solve(0, 0, 0)`.

## Dynamic Programming with Combinatorial Counting
This efficient approach reframes the problem. Instead of counting 'great' partitions directly, we count the total number of partitions and subtract the 'bad' ones. A partition is 'bad' if at least one of its two groups has a sum less than `k`. This transformation allows us to use dynamic programming to solve a subproblem (counting subsets with a small sum), which is much faster than exploring all partitions.
**Time:** O(n * k)
Where `n` is the number of elements in `nums` and `k` is the target sum. The nested loops for the DP calculation are the main contributors to the runtime. · **Space:** O(k)
The space is dominated by the DP array of size `k`.
**Pros:** Highly efficient and passes within the given time limits.; The space complexity is optimized to be linear with `k`.
**Cons:** The logic is indirect and relies on a combinatorial insight which might not be immediately obvious.; Requires careful handling of modular arithmetic.
### Explanation
The core idea is based on the principle of inclusion-exclusion: `Number of Great Partitions = Total Partitions - Bad Partitions`.

First, a critical observation: if the total sum `S` of all elements is less than `2k`, no great partition is possible. In this case, the answer is 0.

Assuming `S >= 2k`, we proceed as follows:
- **Total Partitions:** For each of the `n` elements, we can place it in group 1 or group 2. This gives `2^n` total partitions.
- **Bad Partitions:** A partition `(group1, group2)` is bad if `sum(group1) < k` or `sum(group2) < k`. Because `S >= 2k`, these two conditions are mutually exclusive (if one is true, the other must be false). Therefore, we can simply add their counts.
- **Counting Partitions with a Small Sum Group:** The number of partitions where `sum(group1) < k` is equal to the number of subsets of `nums` that can be formed with a sum less than `k`. By symmetry, this is the same as the number of partitions where `sum(group2) < k`.
- **Dynamic Programming:** We use a DP approach, similar to the 0/1 Knapsack problem, to count the number of subsets with a sum less than `k`. Let `dp[s]` be the number of subsets that sum to `s`.

```java
class Solution {
    public int countPartitions(int[] nums, int k) {
        long totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }

        if (totalSum < 2L * k) {
            return 0;
        }

        int MOD = 1_000_000_007;
        int n = nums.length;

        // dp[s] = number of subsets with sum s
        long[] dp = new long[k];
        dp[0] = 1; // For the empty subset with sum 0

        for (int num : nums) {
            for (int s = k - 1; s >= num; s--) {
                dp[s] = (dp[s] + dp[s - num]) % MOD;
            }
        }

        long smallSumCount = 0;
        for (int s = 0; s < k; s++) {
            smallSumCount = (smallSumCount + dp[s]) % MOD;
        }

        long totalPartitions = power(2, n, MOD);
        long badPartitions = (2 * smallSumCount) % MOD;

        long greatPartitions = (totalPartitions - badPartitions + MOD) % MOD;

        return (int) greatPartitions;
    }

    private long power(long base, long exp, int mod) {
        long res = 1;
        base %= mod;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % mod;
            base = (base * base) % mod;
            exp /= 2;
        }
        return res;
    }
}
```
### Algorithm
1. Calculate the total sum `S` of all elements in `nums`. If `S < 2k`, it's impossible for both groups to have a sum of at least `k`. Return 0.
2. The total number of ways to partition `n` elements into two distinct groups is `2^n`.
3. We will count the number of 'bad' partitions and subtract them from the total. A partition is bad if `sum(group1) < k` or `sum(group2) < k`.
4. Since `S >= 2k`, the conditions `sum(group1) < k` and `sum(group2) < k` are mutually exclusive for any partition. Thus, the number of bad partitions is `(partitions with sum(group1) < k) + (partitions with sum(group2) < k)`.
5. By symmetry, these two counts are identical. We only need to find the number of ways to form a subset (for one group) whose sum is less than `k`.
6. Use dynamic programming to find the number of subsets with a sum `s` for `s < k`. Let `dp[s]` be the number of subsets of `nums` that sum to `s`.
7. Initialize a DP array `dp` of size `k`, with `dp[0] = 1` (for the empty set) and all other elements as 0.
8. Iterate through each `num` in `nums`. For each `num`, update the `dp` array: `for s from k-1 down to num`, `dp[s] = (dp[s] + dp[s - num]) % MOD`.
9. After iterating through all numbers, sum up the values in the `dp` array to get the total number of subsets with a sum less than `k`. Let this be `smallSumCount`.
10. The total number of bad partitions is `2 * smallSumCount`.
11. The number of great partitions is `(power(2, n) - 2 * smallSumCount) % MOD`. Remember to handle potential negative results by adding `MOD` before the final modulo operation.

# Solutions
### Java

```java
class Solution {
private
  static final int MOD = (int)1 e9 + 7;
public
  int countPartitions(int[] nums, int k) {
    long s = 0;
    for (int v : nums) {
      s += v;
    }
    if (s < k * 2) {
      return 0;
    }
    int n = nums.length;
    long[][] f = new long[n + 1][k];
    f[0][0] = 1;
    long ans = 1;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      ans = ans * 2 % MOD;
      for (int j = 0; j < k; ++j) {
        f[i][j] = f[i - 1][j];
        if (j >= v) {
          f[i][j] = (f[i][j] + f[i - 1][j - v]) % MOD;
        }
      }
    }
    for (int j = 0; j < k; ++j) {
      ans = (ans - f[n][j] * 2 % MOD + MOD) % MOD;
    }
    return (int)ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int countPartitions(vector<int> &nums, int k) {
    long s = accumulate(nums.begin(), nums.end(), 0l);
    if (s < k * 2)
      return 0;
    int n = nums.size();
    long f[n + 1][k];
    int ans = 1;
    memset(f, 0, sizeof f);
    f[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
      int v = nums[i - 1];
      ans = ans * 2 % mod;
      for (int j = 0; j < k; ++j) {
        f[i][j] = f[i - 1][j];
        if (j >= v) {
          f[i][j] = (f[i][j] + f[i - 1][j - v]) % mod;
        }
      }
    }
    for (int j = 0; j < k; ++j) {
      ans = (ans - f[n][j] * 2 % mod + mod) % mod;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int: if sum(nums) < k * 2: return 0 mod = 10 ** 9 + 7 n = len(nums) f = [[0] * k for _ in range(n + 1)] f[0][0] = 1 ans = 1 for i in range(1, n + 1): ans = ans * 2 % mod for j in range(k): f[i][j] = f[i - 1][j] if j >= nums[i - 1]: f[i][j] = (f[i][j] + f[i - 1][j - nums[i - 1]]) % mod return (ans - sum(f[- 1]) * 2 + mod) % mod

```