หาผลรวมของเซตย่อยที่แตกต่างกันทั้งหมดของอาร์เรย์ด้วย C++

สมมติว่าเรามีชุดของจำนวนเต็ม ให้หาผลรวมที่แตกต่างกันซึ่งสามารถสร้างได้จากเซตย่อย (Subset) ของชุดที่กำหนด และพิมพ์ตามลำดับจากน้อยไปมาก ผลรวมของสมาชิกอาร์เรย์มีค่าน้อย ให้พิจารณาอาร์เรย์เช่น [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

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

เราจะใช้วิธีการโปรแกรมแบบไดนามิก (Dynamic Programming) เมื่อผลรวมของสมาชิกที่กำหนดมีค่าน้อย เราสามารถสร้างตาราง DP ที่แถวมีขนาดเท่าอาร์เรย์ และคอลัมน์มีขนาดเท่าผลรวมของสมาชิกทั้งหมดในอาร์เรย์ที่กำหนด

ตัวอย่างโค้ด

#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;
                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);
}

ผลลัพธ์

0 1 2 3 4 5 6