इस समस्या में, हमें पूर्णांकों का एक ऐरे और एक संख्या 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 << "ऐरे के तत्वों के योग का उपयोग करके " << N << " उत्पन्न करने के कुल तरीके: "
<< arraySumWays(array, size, N);
return 0;
}
आउटपुट
ऐरे के तत्वों के योग का उपयोग करके 7 उत्पन्न करने के कुल तरीके: 6
