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