ধরুন আমাদের একটি অ-খালি অ্যারে রয়েছে যেখানে শুধুমাত্র ধনাত্মক সংখ্যা রয়েছে, আমাদের খুঁজে বের করতে হবে যে অ্যারেটিকে দুটি উপসেটে বিভক্ত করা যেতে পারে যাতে উভয় উপসেটের উপাদানের যোগফল একই হয়। সুতরাং ইনপুট যদি [1,5,11,5] এর মত হয় তবে আউটপুট সত্য হবে। যেহেতু এই অ্যারেটিকে [1, 5, 5] এবং [11]
হিসাবে বিভক্ত করা যেতে পারেএটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- n :=অ্যারের আকার
- সমষ্টি :=0
- এর জন্য i :=0 থেকে n – 1
- সমষ্টি :=যোগফল + সংখ্যা[i]
- যদি যোগফল বিজোড় হয়, তাহলে মিথ্যা ফেরত দিন
- সমষ্টি :=যোগফল / 2
- একটি বিন্যাস তৈরি করুন যার নাম dp এর সমষ্টি + 1
- dp[0] :=সত্য
- আমি 0 থেকে n – 1
- পরিসরে
- x :=সংখ্যা[i]
- j এর জন্য :=যোগফল j – x
- পর্যন্ত
- dp[j] :=dp[j] বা dp[j - x], যা 0 নয়
- রিটার্ন dp[sum]
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for(int i =0;i<n;i++)sum+=nums[i];
if(sum&1)return false;
sum/=2;
vector <bool> dp(sum+1);
dp[0] = true;
for(int i =0;i<n;i++){
int x = nums[i];
for(int j =sum;j-x>=0;j--){
dp[j]=dp[j] || dp[j-x];
}
}
return dp[sum];
}
};
main(){
Solution ob;
vector<int> v = {1,5,11,5};
cout << ob.canPartition(v);
} ইনপুট
[1,5,11,5]
আউটপুট
1
