Trong bài toán này, chúng ta được cung cấp một chuỗi các số nguyên từ 0 đến 9 và một giá trị đích. Chúng tôi phải in ra các cách mà chúng tôi có thể tạo biểu thức bằng cách sử dụng phép toán +, - và * được đánh giá với giá trị bằng với target.
Hãy lấy một ví dụ để hiểu rõ hơn về chủ đề -
Input: string = “123” , target= 6
Output: { “1+2+3”, “1*2*3” } Để giải quyết vấn đề này, chúng tôi sẽ tạo các biểu thức bằng cách đặt các toán tử nhị phân có thể chấp nhận được giữa các chữ số và sau đó kiểm tra kết quả của biểu thức với giá trị đích.
Chúng tôi sẽ chuyển tất cả các giá trị cho một phương thức đệ quy sẽ đánh giá biểu thức đó. Nếu số bắt đầu từ 0, thì chúng tôi sẽ bỏ qua nó.
Ví dụ
#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;
} Đầu ra
Các biểu thức là -
3+4+5