ধরুন আমাদের পূর্ণসংখ্যার একটি সেট আছে। প্রদত্ত সেটের উপসেট থেকে তৈরি করা যেতে পারে এমন স্বতন্ত্র যোগফল খুঁজুন এবং একটি ঊর্ধ্ব ক্রমে মুদ্রণ করুন। অ্যারে উপাদানের যোগফল ছোট। বিবেচনা করুন অ্যারের উপাদানগুলি [1, 2, 3] এর মতো। আউটপুট হবে 0, 1, 2, 3, 4, 5, 6। স্বতন্ত্র উপসেটগুলি হল {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1 , 3}, {1, 2, 3}, যোগফলের মান হল 0, 1, 2, 3, 3, 5, 4, 6।
এটি সমাধান করার জন্য, আমরা ডায়নামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব। যখন প্রদত্ত উপাদানের যোগফল ছোট হয়, তখন আমরা অ্যারের আকার সহ সারি সহ একটি DP টেবিল তৈরি করতে পারি এবং কলামের আকার প্রদত্ত অ্যারের সমস্ত উপাদানের যোগফল হবে৷
উদাহরণ
#include<iostream>
#include<cstring>
using namespace std;
void displaySubsetSum(int arr[], int n) {
int sum = 0;
for (int i=0; i<n; i++)
sum += arr[i];
bool table[n+1][sum+1];
memset(table, 0, sizeof(table));
for (int i=0; i<=n; i++)
table[i][0] = true;
for (int i=1; i<=n; i++) {
table[i][arr[i-1]] = true;
for (int j=1; j<=sum; j++) {
if (table[i-1][j] == true) {
table[i][j] = true;
table[i][j + arr[i-1]] = true;
}
}
}
for (int j=0; j<=sum; j++)
if (table[n][j]==true)
cout << j << " ";
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
displaySubsetSum(arr, n);
} আউটপুট
0 1 2 3 4 5 6
