मान लीजिए हमारे पास पूर्णांकों का एक सेट है। विशिष्ट योग ढूंढें जो दिए गए सेट के सबसेट से बनाए जा सकते हैं और उन्हें आरोही क्रम में प्रिंट करें। सरणी तत्वों का योग छोटा है। उदाहरण: सरणी [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 टेबल बना सकते हैं जिसमें पंक्तियों में सरणी का आकार और कॉलम में सरणी के सभी तत्वों का योग होगा।
C++ उदाहरण
#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;
if (j + arr[i-1] <= sum)
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);
return 0;
}
आउटपुट
0 1 2 3 4 5 6