C++ ব্যবহার করে একটি দেওয়া সংখ্যার সমষ্টি তৈরির সব কম্বিনেশন খুঁজে বের করা

ধরি আমাদের একটি ধনাত্মক সংখ্যা n আছে। আমাদের সেই সংখ্যাটি তৈরির জন্য সব ধনাত্মক সংখ্যার কম্বিনেশন খুঁজে বের করতে হবে। এখানে আমরা শুধু কম্বিনেশন চাই, পারমুটেশন (permutation) নয়। n = 4 এর জন্য কম্বিনেশনগুলি হবে [1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]

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

এটি আমরা রিকার্শন (recursion) ব্যবহার করে সমাধান করব। আমাদের কম্বিনেশন সংরক্ষণের জন্য একটি অ্যারে থাকবে এবং রিকার্শিভ পদ্ধতিতে সেটি পূরণ করব। প্রতিটি কম্বিনেশন এলিমেন্টের ক্রমবর্ধমান ক্রমে সংরক্ষিত হবে।

উদাহরণ কোড

#include <iostream>
using namespace std;

void getCombination(int arr[], int index, int num, int decrement) {
    if (decrement < 0)
        return;
    
    if (decrement == 0) {
        for (int i = 0; i < index; i++)
            cout << arr[i] << " ";
        cout << endl;
        return;
    }
    
    int prev;
    if (index == 0)
        prev = 1;
    else
        prev = arr[index-1];
    
    for (int k = prev; k <= num; k++) {
        arr[index] = k;
        getCombination(arr, index + 1, num, decrement - k);
    }
}

void findCombinations(int n) {
    int arr[n];
    getCombination(arr, 0, n, n);
}

int main() {
    int n = 4;
    findCombinations(n);
}

আউটপুট

1 1 1 1 1 1 2 1 3 2 2 4