282. Expression Add Operators

Given a string that contains only digits 0-9 and a target value, return all possibilities to addbinary Operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"] "232", 8 -> ["2*3+2", "2+3*2"]"105", 5 -> ["1*0+5","10-5"]"00", 0 -> ["0+0", "0-0", "0*0"]"3456237490", 9191 -> []
Credits:Special thanks to @davidtan1890 for adding this PRoblem and creating all test cases.
Subscribe to see which companies asked this question.
给出一个字符串和目标数，允许使用加减乘法，求出所有能得到目标的计算方法。只想到比较暴力的dfs方法。需要注意的是乘法这种情况，因为乘法优先级比较高，所以前面如果是加减法，则乘法不能是现在的结果*现在的数，而是在前一个结果上加（或减）前一个数×现在的数。所以dfs的参数中还要包含前一个数和前一个操作。还要注意的是“0..0x”的情况是不行的。最后注意的是会出现超出int的范围。
代码：
class Solution{public:	vector<string> addOperators(string num, int target) 	{		string tmp;		dfs(0, tmp, 0, 1, '*', num, target);		return res;	}private:	vector<string> res;	void dfs(int pos, string tmp, long long sum, long long prev, char oper, const string& num, int target)	{		if(pos == num.size()) 		{			if(sum == target)			{				res.push_back(tmp.substr(1));			}			return;		}		for(int i = pos+1; i <= num.size(); ++i)		{				if(i-pos > 1 && num[pos] == '0') break;			long long n = stoll(num.substr(pos, i-pos));			dfs(i, tmp+"+"+num.substr(pos, i-pos), sum+n, n, '+', num, target);			if(pos == 0) continue;			dfs(i, tmp+"-"+num.substr(pos, i-pos), sum-n, n, '-', num, target);			long long cur_sum = (oper == '+' ? sum-prev+prev*n : (oper == '-' ? sum+prev-prev*n : prev*n));			dfs(i, tmp+"*"+num.substr(pos, i-pos), cur_sum, prev*n, oper, num, target);		}	}};