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[target] -1 না হয়, তাহলে dp[target] ফেরত দিন
উত্তর :=0
আমি 0 থেকে সংখ্যার মধ্যে
- যদি টার্গেট>=সংখ্যা[i]
  - উত্তর :=উত্তর + সমাধান(সংখ্যা, লক্ষ্য – সংখ্যা[i], ডিপি)
dp[target] সেট করুন :=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