इस समस्या में, हमें 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
