ধরুন আমাদের কাছে অ-ঋণাত্মক পূর্ণসংখ্যার একটি তালিকা আছে, a1, a2, ..., an, এবং আরেকটি মান, তা হল লক্ষ্য, S। এখন আমাদের 2টি চিহ্ন আছে + এবং - . প্রতিটি পূর্ণসংখ্যার জন্য, আমাদের নতুন প্রতীক হিসাবে + এবং - থেকে একটি বেছে নেওয়া উচিত। পূর্ণসংখ্যার যোগফল টার্গেট মানের S এর সমান করার জন্য আমাদের কতগুলি উপায়ে প্রতীক বরাদ্দ করতে হবে তা খুঁজে বের করতে হবে। সুতরাং যদি সংখ্যাগুলি [1,1,1,1,1], এবং S =3 হয়, তাহলে আউটপুট হবে 5, সংমিশ্রণগুলি হল – 1 + 1 + 1 + 1 + 1 =3, + 1 – 1 + 1 + 1 + 1 =3, + 1 + 1 – 1 + 1 + 1 =3, + 1 + 1 + 1 – 1 + 1 =3, + 1 + 1 + 1 + 1 – 1 =3। তাই তাদের বরাদ্দ করার পাঁচটি উপায় রয়েছে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- 21 x 2001 আকারের একটি টেবিল ডিপি তৈরি করুন, এটি পূরণ করুন – 1। এটি গতিশীল প্রোগ্রামিং পদ্ধতির জন্য ব্যবহার করা হবে
- পুনরাবৃত্ত পদ্ধতি ব্যবহার করা হবে সমাধান()। এটি pos, array v, tempSum এবং প্রকৃত যোগফল S নেবে। এটি নিচের মত কাজ করবে -
- যদি pos অ্যারে v-এর আকারের সমান হয়, তাহলে true ফেরত দিন, যদি s =tempSum, অন্যথায় মিথ্যা
- যদি dp[pos, tempSum + 1000] -1 না হয়, তাহলে dp[pos, tempSum + 1000] ফেরত দিন
- উত্তর :=সমাধান(pos + 1, v, tempSum – v[pos], s) + solve(pos + 1, v, tempSum + v[pos], s)
- dp[pos, tempSum + 1000] =ans
- উত্তর ফেরত দিন
- প্যারামিটার solve(0, nums, 0, s) ব্যবহার করে মূল বিভাগ থেকে solve() কে কল করুন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[21][2001];
int solve(int pos, vector <int> v, int tempSum, int s){
if(pos == v.size()){
return s == tempSum;
}
if(dp[pos][tempSum+1000]!=-1)return dp[pos][tempSum+1000];
int ans = solve(pos+1,v,tempSum-v[pos],s) +solve(pos+1,v,tempSum+v[pos],s);
dp[pos][tempSum+1000] = ans;
return ans;
}
int findTargetSumWays(vector<int>& nums, int s) {
int n = nums.size();
if(s>1000)return 0;
for(int i =0;i<21;i++){
for(int j =0;j<2001;j++){
dp[i][j] = -1;
}
}
return solve(0,nums,0,s);
}
};
main(){
Solution ob;
vector<int> v = {1,1,1,1,1};
cout << ob.findTargetSumWays(v, 3);
} ইনপুট
[1,1,1,1,1] 3
আউটপুট
5
