मान लीजिए कि हमारे पास पूर्णांकों का एक सेट है। दिए गए समुच्चयों के उपसमुच्चय से बनने वाले विशिष्ट योग ज्ञात कीजिए और उन्हें आरोही क्रम में मुद्रित कीजिए। सरणी तत्वों का योग छोटा है। विचार करें कि सरणी तत्व [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