मान लीजिए हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सूची है, a1, a2, ..., an, और एक अन्य मान, जो लक्ष्य (target) है, 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 की एक तालिका dp बनाएं, इसे -1 से भरें। इसका उपयोग डायनामिक प्रोग्रामिंग दृष्टिकोण के लिए किया जाएगा
- पुनरावर्ती विधि का उपयोग किया जाएगा जिसे solve() कहा जाता है। यह pos, सरणी v, tempSum और वास्तविक योग S लेगा। यह नीचे की तरह कार्य करेगा -
- यदि pos सरणी v के आकार के समान है, तो true लौटाएं, यदि s = tempSum, अन्यथा false
- यदि dp[pos, tempSum + 1000] -1 नहीं है, तो dp[pos, tempSum + 1000] लौटाएं
- ans := solve(pos + 1, v, tempSum - v[pos], s) + solve(pos + 1, v, tempSum + v[pos], s)
- dp[pos, tempSum + 1000] = ans
- ans लौटाएं
- मुख्य भाग से solve() को पैरामीटर solve(0, nums, 0, s) का उपयोग करके कॉल करें
उदाहरण (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
