题目：力扣
解题思路：回溯法，
想了好久总算想明白了，太不容易了。。
class Solution { int target; String num; List<String> res; char[] expr; int num_len; public List<String> addOperators(String num, int target) { this.target = target; this.num = num; this.num_len = num.length(); this.res = new ArrayList<String>(); expr = new char[2*num_len]; backtrack(0,0,0,0); return res; } //params : start:开始选取数字的位置 ，expr_len:当前表达式的长度,curValue:当前表达式的算术值 //preValue:前面的选取的数字的数值（带符号的数字，*要注意preValue是前面两个数的乘积，例如当前表达式为1+2，则preValue为2,curValue为3,1-2的话,preValue=-2,curValue = -1,1*2的话，preValue = 1*2=2,curValue = 1*2 = 2） public void backtrack(int start, int expr_len, long curValue, long preValue){ //如果数字用完了，表示表达式完成了 if(start == num_len){ //若当前表达式的值等于target，则添加该表达式，否则返回 if(curValue == target){ res.add(new String(expr, 0, expr_len)); } return; } long n = 0; int index = start; int sign_pos = expr_len; if(start != 0){ expr_len++; } while(index < num_len){ n = n*10 + num.charAt(index) - '0'; if(num.charAt(start) == '0' && index - start > 0){ return; } expr[expr_len] = num.charAt(index); expr_len++; index++; if(start == 0){ backtrack(index,expr_len,n, n); continue; } expr[sign_pos] = '+'; backtrack(index, expr_len, curValue + n, n); expr[sign_pos] = '-'; backtrack(index, expr_len, curValue - n, -n); expr[sign_pos] = '*'; backtrack(index, expr_len, curValue - preValue + preValue*n, preValue*n); } } }
