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

cangjie

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>

countPartitions

Number of Great Partitions

Palindrome Partitioning II

palindrome-partitioning-ii

分割回文串 II

Partition Equal Subset Sum

partition-equal-subset-sum

分割等和子集

Find the Punishment Number of an Integer

find-the-punishment-number-of-an-integer

求一个整数的惩罚数

Array

Dynamic Programming

给你一个正整数数组 <code>nums</code> 和一个整数 <code>k</code> 。

分区 的定义是：将数组划分成两个有序的 组 ，并满足每个元素 恰好 存在于 某一个 组中。如果分区中每个组的元素和都大于等于 <code>k</code> ，则认为分区是一个好分区。

返回 不同 的好分区的数目。由于答案可能很大，请返回对 <code>109 + 7</code> 取余 后的结果。

如果在两个分区中，存在某个元素 <code>nums[i]</code> 被分在不同的组中，则认为这两个分区不同。

&nbsp;

示例 1：

<pre>
输入：nums = [1,2,3,4], k = 4
输出：6
解释：好分区的情况是 ([1,2,3], [4]), ([1,3], [2,4]), ([1,4], [2,3]), ([2,3], [1,4]), ([2,4], [1,3]) 和 ([4], [1,2,3]) 。
</pre>

示例 2：

<pre>
输入：nums = [3,3,3], k = 4
输出：0
解释：数组中不存在好分区。
</pre>

示例 3：

<pre>
输入：nums = [6,6], k = 2
输出：2
解释：可以将 nums[0] 放入第一个分区或第二个分区中。
好分区的情况是 ([6], [6]) 和 ([6], [6]) 。
</pre>

&nbsp;

提示：

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