ผลรวมของผลคูณทุกซับเซ็ตที่เป็นไปได้ใน C++

ภาพรวมปัญหา

หาผลรวมของผลคูณของทุกซับเซ็ต (ยกเว้นเซ็ตว่าง) ของอาร์เรย์ arr[] ขนาด N

ตัวอย่าง

Input: arr[] = {4, 5, 6}
Output: 209
Explanation: 
Subsets: {4},{5},{6},{4,5},{5,6},{4,6},{4,5,6}
Products: 4+5+6+20+30+24+120 = 209

วิธีแก้ปัญหา

วิธีสร้างซับเซ็ตทั้งหมด - O(2ⁿ)

ใช้บิตมาสก์วนทุกซับเซ็ต

วิธีสูตรคณิตศาสตร์ - O(n)

สูตร: ผลรวม = (1+a₁)(1+a₂)...(1+aₙ) - 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);
    return sum - 1;
}

int main() {
    int arr[] = {5, 6, 8, 9};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Sum of product of all subsets = " << productOfSubsetSums(arr, n);
    return 0;
}

ผลลัพธ์

Sum of product of all possible subsets is 3779