C++-এ পার্টিশান সমস্যা: সমান যোগফলের দুটি সাবসেটে বিভাজন

এই সমস্যায় আমাদের একটি অ্যারে দুটি সমান সাবসেটে বিভাজ্য কিনা তা নির্ণয় করতে হবে, অর্থাৎ দুটি সাবসেটের উপাদানগুলোর যোগফল সমান কিনা। পার্টিশান সমস্যা সাবসেট সাম πρόব্লেমের একটি ভেরিয়েন্ট, যা আবার ন্যাপস্যাক সমস্যার ভেরিয়েন্ট। C++ দিয়ে এই সমস্যাটি সমাধান করতে হবে। শর্ত পূরণ হলে "Yes", না হলে "No" রিটার্ন করতে হবে।

ইনপুট

arr[] = {6, 4, 8, 12, 15}

আউটপুট

Is impossible to divide into two subsets of equal sum

সমাধানের পদ্ধতি

রিকার্সিভ পদ্ধতি: সব উপাদানের যোগফল বের করুন। যোগফল বিজোড় হলে বিভাজন সম্ভব নয়। জোড় হলে sum/2 যোগফলের সাবসেট খুঁজুন। প্রতিটি উপাদানের জন্য দুটি পথ: সাবসেটে রাখা বা রাখা না। রিকার্সিভভাবে সমাধান করুন।

উদাহরণ ১ (রিকার্সিভ)

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

bool isSubsetSum(int arr[], int n, int sum) { 
    if (sum == 0) return true; 
    if (n == 0 && sum != 0) return false; 
    if (arr[n - 1] > sum) return isSubsetSum(arr, n - 1, sum); 
    return isSubsetSum(arr, n - 1, sum) || isSubsetSum(arr, n - 1, sum - arr[n - 1]); 
} 

bool findPartiion(int arr[], int n) { 
    int sum = 0; 
    for (int i = 0; i < n; i++) sum += arr[i]; 
    if (sum % 2 != 0) return false; 
    return isSubsetSum(arr, n, sum / 2); 
} 

int main() { 
    int arr[] = {6, 4, 8, 12, 15}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    if (findPartiion(arr, n)) 
        cout << "Is possible to divide into two subsets of equal sum"; 
    else 
        cout << "Is impossible to divide into two subsets of equal sum"; 
    return 0; 
}

আউটপুট

Is impossible to divide into two subsets of equal sum

পদ্ধতি ২: ডাইনামিক প্রোগ্রামিং

যখন উপাদানগুলোর যোগফল ছোট হয়, ডাইনামিক প্রোগ্রামিং দিয়ে দক্ষতার সাথে সমাধান করা যায়। একটি বুলিয়ান অ্যারে part[][] ব্যবহার করে বটম-আপ পদ্ধতিতে সমাধান করা হয়।

উদাহরণ ২ (DP)

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

bool findPartiion(int arr[], int n) { 
    int sum = 0; 
    for (int i = 0; i < n; i++) sum += arr[i]; 
    if (sum % 2 != 0) return false; 
    bool part[sum / 2 + 1] = {0}; 
    for (int i = 0; i < n; i++) { 
        for (int j = sum / 2; j >= arr[i]; j--) { 
            if (part[j - arr[i]] || j == arr[i]) 
                part[j] = 1; 
        } 
    } 
    return part[sum / 2]; 
} 

int main() { 
    int arr[] = {6, 4, 8, 12, 15}; 
    int n = sizeof(arr) / sizeof(arr[0]); 
    if (findPartiion(arr, n)) 
        cout << "Is possible to divide into two subsets of equal sum"; 
    else 
        cout << "Is impossible to divide into two subsets of equal sum"; 
    return 0; 
}

আউটপুট

Is impossible to divide into two subsets of equal sum

উপসংহার

এই টিউটোরিয়ালে আমরা পার্টিশান সমস্যা সমাধানের দুটি পদ্ধতি (রিকার্সিভ এবং DP) শিখেছি। এই কোড জাভা, পাইথন ইত্যাদিতে লেখা যায়।