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() নামে একটি রিকারসিভ ফাংশন আছে, যা অ্যারে, টার্গেট এবং ডাইনামিক প্রোগ্রামিং-এর জন্য আরেকটি অ্যারে নেয়। প্রক্রিয়াটি হবে এইভাবে:
যদি target = 0 হয়, তবে 1 রিটার্ন করুন
যদি dp[target] -1 না হয়, তবে dp[target] রিটার্ন করুন
ans := 0
i = 0 থেকে nums পর্যন্ত
- যদি target >= nums[i] হয়
  - ans := ans + solve(nums, target - nums[i], dp)
dp[target] := 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