282. Expression Add Operators

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 -> []
思路：DFS，但是要保存上一次操作的数字，这样当这次是乘法时：就要先加上去回退到上一步，再重新计算乘法
（这里可能会int变量溢出，用try-catch包围，但catch语句块里不需要做什么，因为溢出就不可能有正确结果）
import java.util.ArrayList;import java.util.List;public class Solution {		public String num;	public int target;	List<String> rst = new ArrayList<String>();	    public List<String> addOperators(String num, int target) {    	this.num = num;    	this.target = target;    	    	helper(0, 0, "", 0);    	    	return rst;    }            public void helper(int start, int eval, String s, int PRe) {    	if(start == num.length() && eval == target) {    		rst.add(s);    		return;    	}    	    	for(int i=start; i<num.length(); i++) {    		try{    		    if(i > start && num.charAt(start) == '0')	break;    		        			int t = Integer.valueOf(num.substring(start, i+1));    			if(start == 0)	{        			helper(i+1, t, s+t, t);        		} else {        			helper(i+1, eval+t, 		s+"+"+t, 	t);        			helper(i+1, eval-t, 		s+"-"+t, 	-t);        			helper(i+1, eval-pre+pre*t, s+"*"+t, 	pre*t);        		}    		} catch(Exception e) {    			    		}    	}    }}