इस समस्या में, हमें पूर्णांकों की एक सरणी और एक संख्या 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