C++-এ সকল সম্ভাব্য সাবসেটের গুণফলের যোগফল

এই সমস্যায়, আমাদের একটি অ্যারে arr[] দেওয়া আছে যা N সংখ্যক উপাদান ধারণ করে। আমাদের কাজ হল সকল সম্ভাব্য সাবসেটের গুণফলের যোগফল বের করার একটি প্রোগ্রাম তৈরি করা।

এখানে, আমরা সকল সাবসেট খুঁজে বের করব এবং তারপর প্রতিটি সাবসেটের সকল উপাদানের গুণফল বের করব। তারপর সব মানগুলো যোগ করে ফাইনাল যোগফল বের করব।

উদাহরণ দিয়ে বোঝা যাক

ইনপুট

arr[] = {4, 5, 6}

আউটপুট

209

ব্যাখ্যা

arr[]-এর সকল সাবসেট:
{4}, {5}, {6}, {4, 5}, {5, 6}, {4, 6}, {4, 5, 6}
গুণফলের যোগফল = (4) + (5) + (6) + (4*5) + (5*6) + (4*6) + (4*5*6)
                = (4) + (5) + (6) + (20) + (30) + (24) + (120)
                = 209

এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হল সেটের সকল সাবসেট খুঁজে বের করা এবং প্রতিটি সেটের উপাদানগুলোর গুণফল ক্যালকুলেট করা। এবং সব গুণফল যোগ করে, সব সাবসেট ট্রাভার্স করার পর ফাইনাল যোগফল ফেরত দেওয়া।

C++ প্রোগ্রাম উদাহরণ (সহজ পদ্ধতি)

#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

এটি নিচের রূপে জেনারালাইজ করা যায়,

n উপাদানের সেটের জন্য,

যোগফল = (1+ e₁) * (1 + e₂) * … * (1 + eₙ) - 1

C++ প্রোগ্রাম উদাহরণ (দক্ষ পদ্ধতি)

#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