C++ ব্যবহার করে অ্যারেতে সমস্ত ভিন্ন সাবসেট (সাবসিকোয়েন্স) যোগফল খুঁজে বের করা

ধরি আমাদের একটি পূর্ণসংখ্যার সেট আছে। সেটের সাবসেট থেকে গঠিত ভিন্ন যোগফল খুঁজে বের করে আরোহী ক্রমে প্রিন্ট করতে হবে। অ্যারে এলিমেন্টগুলোর যোগফল ছোট। অ্যারে এলিমেন্টগুলি মনে করুন [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।

সমাধানের পদ্ধতি

এটি সমাধান করার জন্য আমরা ডাইনামিক প্রোগ্রামিং পদ্ধতি ব্যবহার করব। যেহেতু দেওয়া এলিমেন্টগুলোর যোগফল ছোট, আমরা একটি 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