number-of-great-partitions

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

Algorithms

You are given an array <code>nums</code> consisting of positive integers and an integer <code>k</code>.

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 <code>k</code>.

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

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

&nbsp;
Example 1:

<pre>
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]).
</pre>

Example 2:

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

Example 3:

<pre>
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]).
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= nums.length, k &lt;= 1000</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 109</code></li>
</ul>