सी++ में संयोजन योग 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 होगा।

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

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

उदाहरण(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