এই সমস্যায়, আমাদের 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
