इस समस्या में, हमें N संख्याओं का एक सरणी arr[] दिया जाता है। हमारा काम एक प्रोग्राम बनाना है जो सभी संभावित सबसेट के उत्पादों का योग ढूंढेगा।
यहां, हम सभी उपसमुच्चय प्राप्त करेंगे और फिर प्रत्येक उपसमुच्चय के लिए सभी तत्वों का गुणनफल ज्ञात करेंगे। फिर योग की गणना करने के लिए सभी मान जोड़ें।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट
arr[] = {4, 5, 6} आउटपुट
209
स्पष्टीकरण -
All subsets of arr[] are: {4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
Sum of product
= (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
= (4) + (5) + (6) + (20) + (30) + (24) + (120)
= 209 समस्या को हल करने का एक सरल तरीका यह है कि समुच्चय के सभी उपसमुच्चयों को खोजा जाए और प्रत्येक समुच्चय के तत्वों के गुणनफल की गणना की जाए। और सभी उत्पादों को जोड़ें, सभी सबसेट को पार करने के बाद सभी अंतिम योग लौटाएं।
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#include<iostream>
#include<math.h>
using namespace std;
int findSumProductSubset(int *arr, int set_length) {
unsigned int size = pow(2, set_length);
int sum = 0;
int product;
for(int counter = 1; counter < size; counter++) {
product = 1;
for(int j = 0; j < size; j++) {
if(counter & (1<<j))
product *= arr[j];
}
sum += product;
}
return sum;
}
int main() {
int arr[] = {4, 5, 6};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The sum of the product of all subsets is "<<findSumProductSubset(arr, n);
} आउटपुट
The sum of the product of all subsets is 209
उपरोक्त दृष्टिकोण सभी सबसेट उत्पन्न करता है इसलिए घातीय समय जटिलता है। इसलिए, यह सबसे कुशल तरीका नहीं है।
एक अधिक कुशल दृष्टिकोण समाधान के लिए एक पैटर्न खोजना होगा।
अब, आइए तीन संख्याओं x, y, z का एक सेट देखें।
योग =x + y + z + xy + yz + xz + xyz
योग =x + xz + y + yz + xy + xyz + z + 1 - 1
योग =x(1+z) + y(1+z) + xy(1+z) + 1(z+1) - 1
योग =( x + y + xy + 1 )( 1 + z ) - 1
योग =( x(1 + y) + 1(1+y) )(1+z) - 1
योग =(1 + x) * (1 + y) * (1 + z) - 1
इसे निम्नलिखित तरीके से सामान्यीकृत किया जा सकता है,
एन एलिमेंट सेट के लिए,
योग =(1+ ई1) * (1 + ई2) * ... * (1 + एन) - 1
उदाहरण
हमारे समाधान की कार्यप्रणाली को दर्शाने के लिए कार्यक्रम,
#include <iostream>
using namespace std;
int productOfSubsetSums(int arr[], int n) {
int sum = 1;
for (int i = 0; i < n; ++i )
sum *= (arr[i] + 1);
sum --;
return sum;
}
int main() {
int arr[] = {5, 6, 8 , 9};
int n = sizeof(arr)/sizeof arr[0];
cout<<"Sum of product of all possible subsets is "<<productOfSubsetSums(arr, n);
return 0;
} आउटपुट
Sum of product of all possible subsets is 3779