এই সমস্যায় একটি পজিটিভ ইন্টিজার অ্যারে দেওয়া থাকলে, সেটিকে দুটি সাবসেটে ভাগ করা সম্ভব কিনা যাতে দুটোর সাম সমান।
উদাহরণ: [1,5,11,5] -> আউটপুট true। পার্টিশন: [1,5,5] এবং [11]।
সমাধানের পদ্ধতি (0/1 Knapsack - Subset Sum)
- মোট সাম
sum। যদি বিজোড় হয়,false। - টার্গেট
target = sum / 2। dp[j]= সামjবানানো সম্ভব কিনা।dp[0] = true।- প্রতিটি নাম্বার
numএর জন্য,targetথেকেnumপর্যন্ত পिछানো तरफ লুপ:dp[j] = dp[j] || dp[j-num]।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 != 0) return false;
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
};
int main() {
Solution ob;
vector<int> v = {1, 5, 11, 5};
cout << (ob.canPartition(v) ? "true" : "false");
return 0;
}
ইনপুট
[1,5,11,5]
আউটপুট
true
