题目：
Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary 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 -> []
链接： http://leetcode.com/problems/expression-add-operators/
题解：
给定字符串和target num，求添加不同的运算符，使得字符串经过计算的值等于target num，要求所有的结果。 这道题好像以前小时候玩的数字游戏啊， 现在能用程序解决，真的很高兴。 代码主要参考了discuss里czonzhu的。要处理好几种边界条件，并且这里是用String进行cache，换成StringBuilder的话可能要多写不少行。需要注意的地方是，当i != position，并且position这个char的值为0时，我们不考虑接下来的运算，直接break，这个处理了case： "2" + "05"之类的。还有当position == "0"时，我们不加任何运算符号。因为有乘法运算，所以我们要cache之前的数字， 在backtracking的时候可以方便计算。 这样算下来，是否用doubly linked list来回溯可以处理更多的case，二刷时要尝试。
Time Complexity - (4n)， Space Complexity - (4n)
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> res = new ArrayList<>();
if(num == null || num.length() == 0) {
return res;
}
addOperators(res, "", num, target, 0, 0, 0);
return res;
}
private void addOperators(List<String> res, String path, String numString, int target, int position, long curNum, long lastVal) {
if(position > numString.length()) {
return;
}
if(position == numString.length() && curNum == target) {
res.add(path);
return;
}
for(int i = position; i < numString.length(); i++) {
if(i != position && numString.charAt(position) == '0') { // pruning edge case: "2" + "05", wrong cut
break;
}
long curVal = Long.parseLong(numString.substring(position, i + 1));
if(position == 0) {
addOperators(res, path + curVal, numString, target, i + 1, curNum + curVal, curVal);
} else {
addOperators(res, path + "+" + curVal, numString, target, i + 1, curNum + curVal, curVal);
addOperators(res, path + "-" + curVal, numString, target, i + 1, curNum - curVal, -curVal);
addOperators(res, path + "*" + curVal, numString, target, i + 1, curNum - lastVal + lastVal * curVal, lastVal * curVal);
}
}
}
}
Reference:
https://leetcode.com/discuss/58614/java-standard-backtrace-ac-solutoin-short-and-clear
https://leetcode.com/discuss/58535/17-lines-solution-dfs-c
https://leetcode.com/discuss/58547/accepted-c-solution
https://leetcode.com/discuss/58876/ac-solution-c-short
https://leetcode.com/discuss/61975/elegant-java-solution
https://leetcode.com/discuss/70597/clean-python-dfs-with-comments