এই সমস্যায় নন-নেগেটিভ ইন্টিজার자들의 একটি লিস্ট এবং একটি টার্গেট S দেওয়া থাকলে, প্রতিটি নম্বরের সামনে + বা - চিহ্ন লাগিয়ে যোগফল S করার কতটি উপায় আছে তা বের করতে হবে।
উদাহরণ: nums = [1,1,1,1,1], S = 3 -> আউটপুট 5।
সমাধানের পদ্ধতি (DP / Subset Sum Transformation)
মোট সাম = sum। ধরি P = পজিটিভ সাবসেটের সাম, N = নেগেটিভ সাবসেটের সাম (এবসোলিউট)। P - N = S এবং P + N = sum। যোগ করলে 2P = S + sum => P = (S + sum) / 2। সুতরাং সমস্যাটি変为: কতটি সাবসেটের সাম P? এটি ০/১ ন্যাপস্যাক।
শর্ত: S + sum জোড় হতে হবে এবং S <= sum।
উদাহরণ (C++ - Memoized Recursion)
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int dp[21][2001]; // constraints: n<=20, sum<=1000
int solve(int pos, vector<int>& v, int currSum, int target) {
if (pos == v.size()) return currSum == target ? 1 : 0;
if (dp[pos][currSum + 1000] != -1) return dp[pos][currSum + 1000];
int add = solve(pos + 1, v, currSum + v[pos], target);
int sub = solve(pos + 1, v, currSum - v[pos], target);
return dp[pos][currSum + 1000] = add + sub;
}
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (abs(target) > sum) return 0;
memset(dp, -1, sizeof(dp));
return solve(0, nums, 0, target);
}
};
int main() {
Solution ob;
vector<int> v = {1, 1, 1, 1, 1};
cout << ob.findTargetSumWays(v, 3);
return 0;
}
ইনপুট
[1,1,1,1,1] 3
আউটপুট
5
অপ্টিমাইজেশন: সাবসেট সাম পদ্ধতিতে O(n * sum) টাইম কমপ্লেক্সিটি, যা বেশি দক্ষ।
