原题链接在这里：https://leetcode.com/problems/expression-add-operators/
用DFS, 递归来解两个变量 cur 和 diff, cur 记录当前运算后的结果，diff用来记录最后变化的值。e.g. 2+3*2，即将要运算到乘以2的时候，上次循环的cur = 5, diff = 3, 而要算这个乘2的时候，需要新进行乘法运算，所以需要把diff从cur中先 减掉，在加上新的diff. 新的 diff 是3*2=6.
数字是可以合并出现的，比如"123", 15能返回"12+3".
若是出现 2*05 这种情况，要排除。
Long 和 Integer 都有 Long.valueOf(string)的method.
用Long型是防止溢出。
AC Java:
public class Solution { public List<String> addOperators(String num, int target) { List<String> res = new ArrayList<String>(); dfs(num, target, 0, 0, "", res); return res; } private void dfs(String num, int target, long cur, long diff, String temp, List<String> res){ if(cur == target && num.length() == 0){ res.add(temp); return; } for(int i = 1; i<=num.length(); i++){ String str = num.substring(0,i); if(str.length() > 1 && str.charAt(0) == ‘0‘){ // corner case like 1*05 break; } String next = num.substring(i); if(temp.length() == 0){ dfs(next, target, Long.parseLong(str), Long.parseLong(str), str, res); }else if(temp.length() > 0){ dfs(next, target, cur + Long.valueOf(str), Long.valueOf(str), temp + "+" + str, res); dfs(next, target, cur - Long.valueOf(str), -Long.valueOf(str), temp + "-" + str, res); dfs(next, target, (cur-diff) + diff*Long.valueOf(str), diff*Long.valueOf(str), temp + "*" + str, res); } } } }
LeetCode Expression Add Operators
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/4919251.html