मान लीजिए हमारे पास एक स्ट्रिंग है जिसमें केवल 0 से 9 तक के अंक हैं। और एक लक्ष्य मान दिया गया है। हमें बाइनरी ऑपरेटर +, - और * को अंकों में जोड़ने की सभी संभावनाएं लौटानी हैं ताकि लक्ष्य मान प्राप्त हो सके। तो यदि इनपुट "232" जैसा है और लक्ष्य 8 है, तो उत्तर ["2*3+2", "2+3*2"] होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
एक विधि solve() परिभाषित करें, जो इंडेक्स, s, curr, target, temp, mult लेगी -
यदि idx >= s का आकार, तो,
यदि target, curr के समान है, तो,
temp को ret के अंत में डालें
लौटें
aux := खाली स्ट्रिंग
i := idx से आरंभ करें, जब i < s का आकार, i को 1 से बढ़ाएं करें -
aux = aux + s[i]
यदि aux[0] '0' के समान है और aux का आकार > 1, तो,
निम्न भाग को अनदेखा करें, अगले पुनरावृत्ति पर जाएं
यदि idx, 0 के समान है, तो,
solve(i + 1, s, aux को पूर्णांक के रूप में, target, aux, aux को पूर्णांक के रूप में) को कॉल करें
अन्यथा
solve(i + 1, s, curr + aux को पूर्णांक के रूप में, target, temp + " + " + aux, aux को पूर्णांक के रूप में) को कॉल करें
solve(i + 1, s, curr - aux को पूर्णांक के रूप में, target, temp + " - " + aux, - aux को पूर्णांक के रूप में) को कॉल करें
solve(i + 1, s, curr - mult + mult * aux को पूर्णांक के रूप में, target, temp + " * " + aux, mult * aux को पूर्णांक के रूप में) को कॉल करें
मुख्य विधि से solve(0, num, 0, target, खाली स्ट्रिंग, 0) को कॉल करें
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } typedef long long int lli; class Solution { public: vector <string> ret; void solve(int idx, string s, lli curr, lli target, string temp, lli mult){ //cout << temp << " " << curr << endl; if(idx >= s.size()){ if(target == curr){ ret.push_back(temp); } return; } string aux = ""; for(int i = idx; i < s.size(); i++){ aux += s[i]; if(aux[0] == '0' && aux.size() > 1) continue; if(idx == 0){ solve(i + 1, s, stol(aux), target, aux, stol(aux)); } else { solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux)); solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux)); solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux)); } } } vector<string> addOperators(string num, int target) { solve(0, num, 0, target, "", 0); return ret; } }; main(){ Solution ob; print_vector(ob.addOperators("232", 8)); }इनपुट
"232", 8
आउटपुट
[2+3*2, 2*3+2, ]
