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

<p><strong>Partition</strong> the array into two ordered <strong>groups</strong> such that each element is in exactly <strong>one</strong> group. A partition is called great if the <strong>sum</strong> of elements of each group is greater than or equal to <code>k</code>.</p>

<p>Return <em>the number of <strong>distinct</strong> great partitions</em>. Since the answer may be too large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4], k = 4
<strong>Output:</strong> 6
<strong>Explanation:</strong> 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>

<p><strong class="example">Example 2:</strong></p>

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

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [6,6], k = 2
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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


# With this one write test cases yourself to double-check all the edge cases, you should be fast with this too, recognizing edge cases

# Need to know all the possible subsets with a sum of >= k

# Brute force seems easy -> you include or not with a sum of the other side, but the problem is asking for O(n^2)

# Classic DP problem right with like how many things you can get out of the sack or something like that

# Let's say I choose some nums[i] to be in group 1 -> then my answer is -> how many groups are there to get to j - nums[i] ... j where j is the cur_k and is 0 <= j <= k. If I don't want to include nums[i] into it, then it's just  

# 01 knapsack except the "weight" is the total sum of the other group...so if you take that item, you're choosing to "reduce" the weight of the other group. In 01 knapsack you're saying the weight is the maximum number of "weight" of the things you can hold. Here that maximum weight is really the total_sum - k, from the total_sum how much can I take before it gets less than k. So k >= total_sum - x => x >= total_sum - k, so as an example if my total_sum is 10 and my k is 3, then I can take away 7 from 10 before I get less than 3, I can always take but it's ok

# But unlike 01 knapsack, you want to find all possible combinations, "not an optimal bag"

# If i take this element, then from the cur_weight - element, I choose take how many combinations I can get from that + if I were to not take this element -> which is just the above number

# so dp[i][j] => If I consider items from 0 to i, what are all the possible combinations I can form given that I can work with weight j

# Take the max as you go -> because you can only take 1 of the previous current weight but you want the best one but you can take any of the smaller ones really -> this seems hard

#    0 1 2 3 4 5 6
#  1 0 1 1 1 1 1 1
#  2 0 1 2 2 2 2 2
#  3 0
#  4 0
#  5 0
#  6 0

# I need to ensure if I take the element, that the other bag has at least one other element, if I don't -> then I don't care, but you can guarentee that because the max_weight - k guarentees you have some leftover on the other side

# General problem I'm having is that you're solving for the current problem but then when you solve for a future problem you're not taking into account the combinations of the current problem. Like for [1 2 3 4] 4, you can't make any combinations with [1, 2] to get k = 4 but when you get to 3 you can. But when you get to 3, everythign is 0 above it so it's hard to form the combinations from 0 because it assumes that the previous problems were "possible"

# Overall realization is that doing these two groups thing is too complicated so maybe you should have realized that you needed to reframe the problem or think of something else because it's too complicated to "track" the other and at the same time track your own set where the sum is >= k

# So need to reframe the problem as -> what are all the items that are <= k and subtract those from the total -> with any set problem always try to think of this set subtraction method

# The problem then becomes -> How can I get to this cur_sum (j) given this item (i) and if I include it or not

# Understanding duplicates, need to subtract twice because you need to account for the "other group" which is identical to your group

# There is this tricky bit where if you do j - nums[i] and that's equal to 0, meaning your current number is equal to the sum -> you should do a +1 because it's in its own group...aka the "empty case" wehre dp[0][j] = 1 if the first row is a dummy row -> you can form a empty set for all sums...

# [1], [1, 2], [2], [3], []
class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        if sum(nums) < k * 2:
            return 0
        
        mod = 10**9 + 7
        total_comb = 2**len(nums) % mod
        dp = [[0] * k for _ in range(0, len(nums))]
        
        for i in range(0, len(dp)):
            for j in range(0, k):
                # Not including this number  
                if i > 0:
                    dp[i][j] = dp[i - 1][j]
                    
                if nums[i] <= j:
                    dp[i][j] += 1 if nums[i] == j else dp[i - 1][j - nums[i]]
           
        return (total_comb - (sum(dp[-1]) + 1) * 2) % mod
297