Partition Problems: Equal Subset Sum and K Equal Parts

def canPartition(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    nums.sort(reverse=True)  # large first = better pruning

    def bt(idx, remaining):
        if remaining == 0: return True
        if remaining < 0 or idx >= len(nums): return False
        # Skip: if nums[idx] == nums[idx-1], we already tried including nums[idx-1]
        if idx > 0 and nums[idx] == nums[idx-1]:
            return bt(idx+1, remaining)
        return bt(idx+1, remaining-nums[idx]) or bt(idx+1, remaining)

    return bt(0, target)

# DP approach O(n * target) — often faster
def canPartitionDP(nums):
    total = sum(nums)
    if total % 2: return False
    target = total // 2
    dp = {0}
    for n in nums:
        dp = dp | {x + n for x in dp}
    return target in dp

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k: return False
    target = total // k
    nums.sort(reverse=True)
    if nums[0] > target: return False
    buckets = [0] * k
    n = len(nums)

    def bt(idx):
        if idx == n: return True
        seen = set()
        for b in range(k):
            if buckets[b] in seen: continue  # skip duplicate bucket states
            if buckets[b] + nums[idx] <= target:
                seen.add(buckets[b])
                buckets[b] += nums[idx]
                if bt(idx + 1): return True
                buckets[b] -= nums[idx]
        return False

    return bt(0)

#include <bits/stdc++.h>
using namespace std;

bool canPartitionKSubsets(vector<int>& nums, int k) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % k) return false;
    int target = sum / k;
    sort(nums.rbegin(), nums.rend());
    if (nums[0] > target) return false;
    int n = nums.size();
    vector<int> buckets(k, 0);

    function<bool(int)> bt = [&](int idx) -> bool {
        if (idx == n) return true;
        set<int> seen;
        for (int b = 0; b < k; b++) {
            if (seen.count(buckets[b])) continue;
            if (buckets[b] + nums[idx] <= target) {
                seen.insert(buckets[b]);
                buckets[b] += nums[idx];
                if (bt(idx + 1)) return true;
                buckets[b] -= nums[idx];
            }
        }
        return false;
    };
    return bt(0);
}