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);		}	}};