Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में संयोजन योग IV

समस्या

मान लीजिए हमारे पास एक पूर्णांक सरणी है जिसमें सभी धनात्मक संख्याएँ हैं और सभी तत्व अद्वितीय हैं, उन संभावित संयोजनों की संख्या ढूंढें जिनका योग धनात्मक पूर्णांक लक्ष्य के बराबर हो।

उदाहरण के लिए, यदि सरणी [1, 2, 3] है और लक्ष्य 4 है, तो संभावित संयोजन होंगे [[1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [1,3], [3,1], [2, 2]], इसलिए आउटपुट 7 होगा।

समाधान दृष्टिकोण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

  • मान लीजिए हमारे पास solve() नामक एक पुनरावर्ती फ़ंक्शन है, जो सरणी, लक्ष्य और डायनामिक प्रोग्रामिंग के लिए एक अन्य सरणी लेता है। प्रक्रिया इस प्रकार होगी:
  • यदि लक्ष्य = 0, तो 1 लौटाएं
  • यदि dp[लक्ष्य] -1 नहीं है, तो dp[लक्ष्य] लौटाएं
  • ans := 0
  • i को 0 से nums तक लूप में
    • यदि लक्ष्य >= nums[i]
      • ans := ans + solve(nums, लक्ष्य - nums[i], dp)
  • dp[लक्ष्य] := ans सेट करें
  • ans लौटाएं

उदाहरण (C++):

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; class Solution { public:    int combinationSum4(vector<int>& nums, int target) {       vector <int> dp(target + 1, -1);       return helper(nums, target, dp);    }    int helper(vector <int>& nums, int target, vector <int>& dp){       if(target == 0)return 1;       if(dp[target] != -1)return dp[target];       int ans = 0;       for(int i = 0; i < nums.size(); i++){          if(target >= nums[i]){             ans += helper(nums, target - nums[i], dp);          }       }       return dp[target] = ans;    } }; main(){    Solution ob;    vector<int> v = {1,2,3};    cout << ob.combinationSum4(v, 4); }

इनपुट

[1,2,3] 4

आउटपुट

7
  1. - C++ में संयोजन योग II (Combination Sum II)

    मान लीजिए हमारे पास उम्मीदवार संख्याओं का एक समूह है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या। हमें उम्मीदवारों में उन सभी अद्वितीय संयोजनों को ढूंढना है जहां उम्मीदवार संख्याओं का योग दिए गए लक्ष्य के बराबर हो। वही संख्या उम्मीदवारों से एक से अधिक बार नहीं चुनी जाएगी। यदि तत्व [2,3,6,7,8] हैं औ

  1. - C++ में एलिक्वॉट योग (Aliquot Sum)

    यहां हम देखेंगे कि एलिक्वॉट योग क्या है? n का एलिक्वॉट योग n को छोड़कर n के सभी पूर्ण गुणनखंडों का योग है। उदाहरण के लिए, यदि संख्या 20 है, तो पूर्ण गुणनखंड (1, 2, 4, 5, 10) हैं। तो एलिक्वॉट योग 22 है। एक दिलचस्प तथ्य यह है कि, यदि किसी संख्या का एलिक्वॉट योग संख्या स्वयं है, तो वह संख्या एक पूर्ण

  1. - पायथन में कॉम्बिनेशन सम

    मान लीजिए हमारे पास उम्मीदवार संख्याओं का एक समूह है (सभी तत्व अद्वितीय हैं) और एक लक्ष्य संख्या। हमें उम्मीदवारों में उन सभी अद्वितीय संयोजनों को ढूंढना है जहां उम्मीदवार संख्याओं का योग दिए गए लक्ष्य के बराबर हो। वही संख्या उम्मीदवारों से असीमित बार चुनी जा सकती है। इसलिए यदि तत्व [2,3,6,7] हैं और