इस समस्या में, हमें 0 से 9 तक पूर्णांकों की एक स्ट्रिंग और एक लक्ष्य मान दिया जाता है। हमें उन तरीकों को प्रिंट करना होगा जिसमें हम +, -, और * ऑपरेशन का उपयोग करके अभिव्यक्ति उत्पन्न कर सकते हैं जिसका मूल्यांकन लक्ष्य के बराबर मूल्य के लिए किया जाता है।
आइए विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
Input: string = “123” , target= 6
Output: { “1+2+3”, “1*2*3” } इस समस्या को हल करने के लिए, हम सभी संभावित बाइनरी ऑपरेटरों को अंकों के बीच रखकर और फिर लक्ष्य मान के साथ एक्सप्रेशन के परिणाम की जांच करके एक्सप्रेशन बनाएंगे।
हम सभी मानों को एक पुनरावर्ती विधि में पास करेंगे जो परिणामी अभिव्यक्ति का मूल्यांकन करेगा। अगर संख्या 0 से शुरू होती है, तो हम इसे अनदेखा कर देंगे।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void generateExpressionForTarget(vector<string>& res, string curExp,
string input, int target, int pos,int curVal, int last){
if (pos == input.length()){
if (curVal == target)
res.push_back(curExp);
return;
}
for (int i = pos; i < input.length(); i++){
if (i != pos && input[pos] == '0')
break;
string part = input.substr(pos, i + 1 - pos);
int cur = atoi(part.c_str());
if (pos == 0)
generateExpressionForTarget(res, curExp + part, input, target, i + 1, cur, cur);
else{
generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
}
}
}
vector<string>generateExpression(string input, int target){
vector<string> res;
generateExpressionForTarget(res, "", input, target, 0, 0, 0);
return res;
}
int main(){
string input = "345";
int target = 12;
cout<<"The expressions are: \n";
vector<string> res = generateExpression(input, target);
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
cout << endl;
return 0;
} आउटपुट
भाव हैं -
3+4+5