이 문제에서는 N개의 숫자로 구성된 배열 ar[]가 제공됩니다. 우리의 임무는 가능한 모든 하위 집합의 곱의 합을 찾는 프로그램을 만드는 것입니다.
여기에서 모든 하위 집합을 찾은 다음 각 하위 집합에 대한 모든 요소의 곱을 찾습니다. 그런 다음 모든 값을 더하여 합계를 계산합니다.
문제를 이해하기 위해 예를 들어 보겠습니다.
입력
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
이것은 다음과 같은 방식으로 일반화될 수 있습니다.
n개의 요소 집합에 대해
합계 =(1+ e1) * (1 + e2) * ... * (1 + en) - 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