力扣 282 给表达式添加运算符

题意：给定一个数字字符串和指定的值，对字符串添加＋，－，＊来获得指定值

思路：递归遍历每一个数的每一个符号组合

思想：数学方法

复杂度：时间O（nⁿ)，空间O(n)

class Solution {
    List<String> res = new ArrayList();
    public List<String> addOperators(String num, int target) {
        get(new StringBuilder(), 0, num, 0, 0, (long) target);
        return res;
    }
    
    void get(StringBuilder temp, int index, String num, long pre, long sum, long target) {
        if(index == num.length() && sum == target) {
            res.add(temp.toString());
            return;
        }
        int len = temp.length();
        for(int i=index;i<num.length();i++) {
            if(i>index && num.charAt(index) == '0')
                return;
            long cur = Long.parseLong(num.substring(index, i+1));
            if(cur > Integer.MAX_VALUE)
                return;
            temp.setLength(len);
            if(temp.length() == 0) {
                get(temp.append(cur), i+1, num, cur, cur, target);
            } else {
                get(temp.append("+").append(cur), i+1, num, cur, sum + cur, target);
                temp.setLength(len);
                get(temp.append("-").append(cur), i+1, num, -cur, sum - cur, target);
                temp.setLength(len);
                get(temp.append("*").append(cur), i+1, num, pre*cur, sum - pre + pre*cur, target);
            }
        }
    }
}