Number of Great Partitions solution and explanation

from itertools import combinations

def greatPartitions(nums, k):
    def valid_partition(partition1, partition2):
        return sum(partition1) >= k and sum(partition2) >= k

    total_partitions = 0
    n = len(nums)
    all_partitions = combinations(nums, n // 2)
    for part1 in all_partitions:
        part2 = [x for x in nums if x not in part1]
        if valid_partition(part1, part2):
            total_partitions += 1

    return total_partitions % (10**9 + 7)

nums = [1, 2, 3, 4]
k = 4
print(greatPartitions(nums, k))

import java.util.*;

public class Main {

    public int greatPartitions(int[] nums, int k) {
        int count = 0;
        int n = nums.length;

        for (int i = 0; i < (1 << n); i++) {
            List<Integer> group1 = new ArrayList<>();
            List<Integer> group2 = new ArrayList<>();

            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) > 0) {
                    group1.add(nums[j]);
                } else {
                    group2.add(nums[j]);
                }
            }

            if (sum(group1) >= k && sum(group2) >= k) {
                count++;
            }
        }

        return count % (int)(1e9 + 7);
    }

    private int sum(List<Integer> group) {
        return group.stream().mapToInt(Integer::intValue).sum();
    }

    public static void main(String[] args) {
        Main mainObj = new Main();
        int[] nums = {1, 2, 3, 4};
        int k = 4;
        System.out.println(mainObj.greatPartitions(nums, k));
    }
}

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

class Solution {
public:
    int greatPartitions(vector<int>& nums, int k) {
        const int MOD = 1e9 + 7;
        int n = nums.size();
        vector<int> current(k + 1, 0);
        vector<int> next(k + 1, 0);
        current[0] = 1; // One way to achieve sum 0 is using nothing

        for (int num : nums) {
            next = current;
            for (int sum = 0; sum <= k - num; ++sum) {
                next[sum + num] = (next[sum + num] + current[sum]) % MOD;
            }
            current = next;
        }

        int result = 0;
        for (int sum = k; sum <= k; ++sum) {
            result = (result + current[sum]) % MOD;
        }

        // Count opposite sums (i.e., total - sum)
        result = (result * result) % MOD;
        return result;
    }
};

int main() {
    Solution sol;
    vector<int> nums = {1, 2, 3, 4};
    int k = 4;
    cout << sol.greatPartitions(nums, k) << endl;
    return 0;
}

function greatPartitions(nums, k) {
    const MOD = 1e9 + 7;
    const dp = Array(k + 1).fill(0);
    dp[0] = 1;

    for (let num of nums) {
        for (let sum = k; sum >= num; sum--) {
            dp[sum] = (dp[sum] + dp[sum - num]) % MOD;
        }
    }

    let result = 0;
    for (let sum = k; sum <= k; sum++) {
        result = (result + dp[sum]) % MOD;
    }

    return (result * result) % MOD;
}

const nums = [1, 2, 3, 4];
const k = 4;
console.log(greatPartitions(nums, k)); // Output: 6

func countPartitions(nums []int, k int) int {
	s := 0
	for _, v := range nums {
		s += v
	}
	if s < k*2 {
		return 0
	}
	const mod int = 1e9 + 7
	n := len(nums)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k)
	}
	f[0][0] = 1
	ans := 1
	for i := 1; i <= n; i++ {
		v := nums[i-1]
		ans = ans * 2 % mod
		for 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 j := 0; j < k; j++ {
		ans = (ans - f[n][j]*2%mod + mod) % mod
	}
	return ans
}