মডিউল ১৯_৫ঃ Equal Sum Partition

এখন আমরা সবসেট সাম এর একটা ভেরিয়েশন নিয়ে চিন্তা করবো।

আমাকে একটা এ্যারে দেওয়া থাকবে। আমার বলতে হবে যে এই এ্যারেকে এমন দুইটা সাবসেটে ভাগ করা সম্ভব কিনা যারে তাদের সাম সমান হয়।

A = {1,4,4,9}

আমরা চাইলে উপরের উদাহরন কে {1,4,4} আর {9} দুইটা সাবসেটে ভাগ করতে পারি।

এখন চিন্তা করি এটা কিভাবে করা সম্ভব। আমরা এটার জন্য প্রথমে পুরো এ্যারে এর টোটাল সাম বের করি।

ধরি টোটাল সাম = s

এখন ধরি সাবসেট গুলোর সাম = x

তাহলে আমরা বলতে পারি যে 2x = s

তাহলে x = s/2

তাহলে আমরা বলতে পারি যে সাবসেট গুলোর সাম হওয়া উচিত টোটাল সাম এর অর্ধেক।

তাহলে আমরা এখন বলতে পারি যে যদি আমরা টোটাল সাম এর অর্ধেক বানাইতে পারে এমন সাবসেট খুঁজি তাহলেই পেয়ে যাবো বানানো সম্ভব কিনা।

// Some code
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int s = 0;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        s += a[i];
    }
    if (s % 2 == 0)
    {
        int sum = s / 2;
        bool dp[n + 1][sum + 1];
        dp[0][0] = true;
        for (int i = 1; i <= sum; i++)
            dp[0][i] = false;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j <= sum; j++)
            {
                if (a[i - 1] <= j)
                {
                    dp[i][j] = dp[i - 1][j - a[i - 1]] || dp[i - 1][j];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        if (dp[n][sum])
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    else
    {
        cout << "NO" << endl;
    }
    return 0;
}