本文主要是介绍282给表达式添加运算符（递归回溯——困难），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1、题目描述
给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。
2、示例
输入: num = "123", target = 6
输出: ["1+2+3", "1*2*3"]
3、题解
基本思想：递归回溯，暴力遍历所有的可能性，时间复杂度O(4^N)
class Solution {
public:vector<string> res;vector<string> addOperators(string num, int target) {//基本思想：递归回溯，暴力遍历所有的可能性，时间复杂度O(4^N)string s="";Recursion(num,target,0,0,1,s);return res;}void Recursion(string& num,int target,int index,long cur,long prenum,string& s){//index表示当前遍历num的下标，cur表示当前计算结果，s表示加上运算符的字符串，prenum表示上一步的操作数if(index==num.size()){if(cur==target)res.push_back(s);return;}string temp;//以当前下标index为起点，遍历下一个操作数的所有可能情况for (int i = index; i < num.size(); i++){string val = num.substr(index, i - index + 1);long n = stol(val); //val转化为数字//第一个数字，不需要加符号if (index == 0) {temp=s+val;Recursion(num,target,i+1,n,n,temp);} else {// +temp=s+"+"+val;Recursion(num,target,i+1,cur+n,n,temp);// -temp=s+"-"+val;Recursion(num,target,i+1,cur-n,-n,temp);// *，乘法分配率高于加减，所以将上一步的操作数减去，重新计算temp=s+"*"+val;Recursion(num,target,i+1,cur-prenum+prenum*n,prenum*n,temp);}//以0开头的数字只能是0自己这一种情况，其他情况不允许if (val=="0") return;}return;}
};
这篇关于282给表达式添加运算符（递归回溯——困难）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
