এই সমস্যায়, আমাদের একটি n আকারের অ্যারে এবং একটি পজিটিভ ইন্টিজার r দেওয়া আছে। আমাদের কাজ হল অ্যারেতে উপাদানগুলো থেকে r আকারের সব সম্ভাব্য কম্বিনেশন প্রিন্ট করা।
একটি উদাহরণ নিয়ে সমস্যাটি বুঝতে চাই −
Input: {5,6,7,8} ; r = 3 Output : {5,6,7}, {5,6,8}, {5,7,8}, {6,7,8}
এই সমস্যা সমাধানের একটি পদ্ধতি হলো উপাদানগুলো ফিক্স করে এবং তারপর অন্যগুলোর ওপর লুপ বা রিকার্শন করে সব কম্বিনেশন বের করা। এতে, আমাদের শুধু প্রথম n-r+1 উপাদানগুলো ফিক্স করতে হবে এবং বাকিগুলোর ওপর লুপ বা রিকার্শন করতে হবে।
উদাহরণ
#include<iostream> using namespace std; void printRElementCombination(int arr[], int combination[], int start, int end, int index, int r){ if (index == r){ cout<<"{ "; for (int j = 0; j < r; j++) cout << combination[j] << " "; cout<<"}\t"; return; } for (int i = start; i <= end && end - i + 1 >= r - index; i++){ combination[index] = arr[i]; printRElementCombination(arr, combination, i+1, end, index+1, r); } } int main(){ int arr[] = {1, 2, 3, 4, 5}; int r = 3; int n = 5; int combination[r]; cout<<"The combination is : \n"; printRElementCombination(arr, data, 0, n-1, 0, r); }
আউটপুট
কম্বিনেশনগুলো হল −
{ 1 2 3 } { 1 2 4 } { 1 2 5 } { 1 3 4 } { 1 3 5 } { 1 4 5 } { 2 3 4 } { 2 3 5 } { 2 4 5 } { 3 4 5 }
এই সমস্যা সমাধানের অন্য পদ্ধতিগুলো হতে পারে করেন্ট এলিমেন্ট কম্বিনেশনে ইনক্লুড হবে কিনা চেক করে_requried সাইজের সব কম্বিনেশন প্রিন্ট করা। আইডিয়া একই, আমরা এলিমেন্টের ওপর রিকার্শন করব এবং কম্বিনেশন কম্বো অ্যারেতে সংরক্ষণ করব। কিন্তু এলিমেন্ট ফিক্স করা হয়নি।
নিচের প্রোগ্রামটি সমস্যাটি আরও বোঝার সহজ করবে −
উদাহরণ
#include <iostream> using namespace std; void combinationUtil(int arr[], int n, int r, int index, int combo[], int i){ if (index == r){ cout<<"{"; for (int j = 0; j < r; j++) cout << combo[j] << " "; cout<<"}\t"; return; } if (i >= n) return; combo[index] = arr[i]; combinationUtil(arr, n, r, index + 1, combo, i + 1); combinationUtil(arr, n, r, index, combo, i+1); } int main(){ int arr[] = {1, 2, 3, 4, 5}; int r = 3; int n = 5; int combo[r]; cout<<"The combination is : \n"; combinationUtil(arr, n, r, 0, combo, 0); return 0; }
আউটপুট
কম্বিনেশনগুলো হল −
{1 2 3 } {1 2 4 } {1 2 5 } {1 3 4 } {1 3 5 } {1 4 5 } {2 3 4 } {2 3 5 } {2 4 5 } {3 4 5 }
