মডিউল ১৯_৩ঃ Count of Subset Sum

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

টপ ডাউন এর ক্ষেত্রে আমরা দেখবো যে কয়টা ০ রিটার্ন আসছে।

এখানে দেখা যায় যে 4,2,1 ও 6,1 এই দুই পাথ এ আমরা ০ পাচ্ছি। আমরা তাহলে এই দুইটাকে কাউন্ট করবো।

// Some code
    if (a[n - 1] <= s)
    {
        int op1 = subset_sum(n - 1, a, s - a[n - 1]);
        int op2 = subset_sum(n - 1, a, s);
        return dp[n][s] = op1 + op2;
    }

এর আগে আমরা OR অপারেশন বের করতাম। এখন শুধু যোগ করবো। এতটুকু করলেই হয়ে যাবে।

এবার দেখি Bottom up এর ক্ষেত্রে কি করতে হবে।

Bottom up এর ক্ষেত্রে আমরা টেবিল এর লাস্ট কলামটার দিকে দেখবো ।।

একদম লাস্ট ইন্ডেক্সে যে ভ্যালু পাবো সেটাই আমার আন্সার। এখানে ৪,২,১ মিলে ৭ হয় আর ৬,১ মিলে।

// Some code
     for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; 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];
            }
        }
    }

এখানেও আমরা OR এর জায়গায় যোগ করছি।

সম্পূর্ণ কোডঃ

// Some code
#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int subset_sum(int n, int a[], int s)
{
    if (n == 0)
    {
        if (s == 0)
            return 1;
        else
            return 0;
    }
    if (dp[n][s] != -1)
        return dp[n][s];
    if (a[n - 1] <= s)
    {
        int op1 = subset_sum(n - 1, a, s - a[n - 1]);
        int op2 = subset_sum(n - 1, a, s);
        return dp[n][s] = op1 + op2;
    }
    else
    {
        return dp[n][s] = subset_sum(n - 1, a, s);
    }
}
int main()
{
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int s;
    cin >> s;
    dp[0][0] = true;
    for (int i = 1; i <= s; i++)
    {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; 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];
            }
        }
    }
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}