এই সমস্যায়, আমাদেরকে পূর্ণসংখ্যার একটি অ্যারে এবং একটি সংখ্যা N দেওয়া হয়েছে। আমাদের কাজ হল অ্যারের উপাদানগুলি যোগ করে N উৎপন্ন করার মোট সংখ্যা গণনা করা। সমস্ত সংমিশ্রণ এবং পুনরাবৃত্তি অনুমোদিত।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট
arr = {1, 3, 5} N = 6 আউটপুট
8
ব্যাখ্যা
উপায় হল -
5+1, 1+5, 3+3, 3+1+1+1, 1+3+1+1, 1+1+3+1, 1+1+1+3, 1+1+1+1+1+1
এই সমস্যাটি সমাধান করার জন্য, আমাদের একটি ভিন্ন পদ্ধতি ব্যবহার করতে হবে কারণ সমস্ত ধরণের সংমিশ্রণকে আলাদাভাবে বিবেচনা করা হবে, তাই যদি সংখ্যাটি অ্যারের 4 উপাদানের যোগফল হয় 4টি ভিন্ন উপায় বিবেচনা করা হয় (উদাহরণ হিসাবে দেখানো হয়েছে)। এই ধরনের সমস্যা সমাধানের জন্য, আমাদের গতিশীল প্রোগ্রামিং পদ্ধতি ব্যবহার করতে হবে এবং নীচের প্রোগ্রামটি বাস্তবায়ন দেখাবে।
উদাহরণ
#include <iostream>
#include <cstring>
using namespace std;
int arraySumWays(int array[], int size, int N){
int count[N + 1];
memset(count, 0, sizeof(count));
count[0] = 1;
for (int i = 1; i <= N; i++)
for (int j = 0; j < size; j++)
if (i >= array[j])
count[i] += count[i - array[j]];
return count[N];
}
int main() {
int array[] = {1, 5, 6};
int size = sizeof(array) / sizeof(array[0]);
int N = 7;
cout<<"Total number of ways inwhich "<<N<<" can be generated using sum of elements of array is " <<arraySumWays(array, size, N);
return 0;
} আউটপুট
Total number of ways inwhich 7 can be generated using sum of elements of array is 6
