सी++ में लक्ष्य योग

मान लीजिए कि हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सूची है, 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, सरणी v, tempSum और वास्तविक योग S लेगा। यह नीचे की तरह कार्य करेगा -
यदि pos सरणी v के आकार के समान है, तो सत्य लौटाएं, यदि s =tempSum, अन्यथा असत्य
यदि dp[pos, tempSum + 1000] -1 नहीं है, तो dp[pos, tempSum + 1000] वापस करें।
उत्तर :=हल करें(pos + 1, v, tempSum – v[pos], s) + हल करें (pos + 1, v, tempSum + v[pos], s)
dp[pos, tempSum + 1000] =ans
वापसी उत्तर
पैरामीटर सॉल्व(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