# 0282. Expression Add Operators
###### tags: `Leetcode` `Hard` `FaceBook` `Backtracking`
Link: https://leetcode.com/problems/expression-add-operators/
## 思路 $O(N×4^N)$ $O(N)$
backtracking
要注意的问题有：
1. 用long存数字而不是int，避免overflow
2. 数字不能有leading zero
3. 如何处理乘法: 遇到乘法就把上一个加上去的数字减掉然后加上乘法的result

时间复杂度：每个位置有四种可能，$+-*$或者和后面的数字组成一个数，对于每一种可能都要花$O(N)$的时间StringBuilder.toString()
## Code

class Solution {
    public List<String> addOperators(String num, int target) {
        List<String> res = new ArrayList<>();
        StringBuilder expr = new StringBuilder();
        backtracking(res, expr, num, target, 0, 0, 0);
        return res;
    }
    private void backtracking(List<String> res, StringBuilder expr, String num, int target, long calcVal, long prevNum, int pos){
        if(pos==num.length() && calcVal==target){
            res.add(expr.toString());
            return;
        }
        int len = expr.length();
        for(int i = pos;i < num.length();i++){
            //corner case: if char at start is 0, then the number can only be zero, without this if, we will get a number with leading zero.
            if(i!=pos && num.charAt(pos)=='0'){
                break;
            }
            long curr = Long.parseLong(num.substring(pos, i+1));
            if(pos==0){
                backtracking(res, expr.append(curr), num, target, curr, curr, i+1);
                expr.setLength(len);
            }
            else{
                backtracking(res, expr.append("+").append(curr), num, target, calcVal+curr, curr, i+1);
                expr.setLength(len);
                backtracking(res, expr.append("-").append(curr), num, target, calcVal-curr, -curr, i+1);
                expr.setLength(len);
                backtracking(res, expr.append("*").append(curr), num, target, calcVal-prevNum+prevNum*curr, prevNum*curr, i+1);
                expr.setLength(len);
            }
        }
    }
}