C++-এ Partition to K Equal Sum Subsets

এই সমস্যায় একটি পূর্ণসংখ্যার অ্যারে এবং পজিটিভ ইন্টিজার k দেওয়া থাকলে, অ্যারেটিকে kটি নন-এম্পটি সাবসেটে ভাগ করা সম্ভব কিনা যাতে সব সাবসেটের যোগফল সমান, তা চেক করতে হবে।

উদাহরণ: nums = [4,3,2,3,5,2,1], k = 4 -> আউটপুট true (১)। সাবসেটগুলো: [5], [1,4], [2,3], [2,3]।

সমাধানের পদ্ধতি (Bitmask DP)

n = nums.size()। মোট সাবসেট 2^n।
dp[mask] = ওই মাস্কটি ভ্যালিড কিনা। total[mask] = ওই মাস্কের সাম।
sum = মোট যোগফল। যদি sum % k != 0 বা max(nums) > sum/k হলে false।
target = sum / k।
dp[0] = true।
সব মাস্ক 0 থেকে 2^n - 1 পর্যন্ত ইটারেট করুন। যদি dp[mask] true হয়, তবে বাকি এলিমেন্টগুলো যোগ করে নতুন মাস্ক বানান। যদি nums[j] <= target - (total[mask] % target) হয়, তবে dp[new_mask] = true।
শেষে dp[(1< চেক করুন।


উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int n = nums.size();
        vector<bool> dp(1 << n, false);
        vector<int> total(1 << n, 0);
        sort(nums.begin(), nums.end());
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % k != 0 || nums.back() > sum / k) return false;
        dp[0] = true;
        int target = sum / k;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (!dp[mask]) continue;
            for (int j = 0; j < n; j++) {
                int newMask = mask | (1 << j);
                if (newMask != mask) {
                    int curSum = total[mask] % target;
                    if (nums[j] <= target - curSum) {
                        dp[newMask] = true;
                        total[newMask] = total[mask] + nums[j];
                    } else break; // sorted array, so further j will be larger
                }
            }
        }
        return dp[(1 << n) - 1];
    }
};

int main() {
    Solution ob;
    vector<int> v = {4, 3, 2, 3, 5, 2, 1};
    cout << (ob.canPartitionKSubsets(v, 4) ? "true" : "false");
    return 0;
}
ইনপুট
[4,3,2,3,5,2,1] 4
আউটপুট
true