Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

&nbsp;
Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.


Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.


Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.


&nbsp;
Constraints:


	1 &lt;= num.length &lt;= 10
	num consists of only digits.
	-231 &lt;= target &lt;= 231 - 1


class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        s=num[0]
        q=["+","-","*",""]
        ans=[]
        def cal(w):
            i=1
            while i<len(w)-1:
                if w[i]=='*':
                    q=int(w[i-1])*int(w[i+1])
                    del w[i+1]
                    del w[i]
                    w[i-1]=q
                    continue
                i+=2
            i=1 
            while i<len(w)-1:
                if w[i]=='+':
                    q=int(w[i-1])+int(w[i+1])
                    del w[i+1]
                    del w[i]
                    w[i-1]=q
                    continue
                elif w[i]=='-':
                    q=int(w[i-1])-int(w[i+1])
                    del w[i+1]
                    del w[i]
                    w[i-1]=q
                    continue
                i+=2
            return w
        def dfs(s,i):
            nonlocal ans
            if i==len(num):
                x=''
                myl=[]
                for i in s:
                    if i not in ['+','-','*']:
                        x+=i
                    else:
                        myl.append(int(x))
                        myl.append(i)
                        x=''
                myl.append(int(x))
                print(myl)
                a=cal(myl)
                print(a)
                if a[0]==target:
                    ans.append(s)
                return
            for j in q:
                dfs(s+j+num[i],i+1)
        dfs(s,1)
        return ans
class Solution {
    String s;
    List<String>result;
    int target;
    public void operator(int i,int prev,long prod,long mid,String exp,List<Long>l){
        if(i==l.size()){
            if(mid+prod==target)
                result.add(exp);
            return;
        }
        if(prev==-1){
            operator(i+1,0,-1*l.get(i)*l.get(i-1),mid+l.get(i-1),exp+"*"+l.get(i),l);
        }else if(prev==1){
            operator(i+1,0,l.get(i)*l.get(i-1),mid-l.get(i-1),exp+"*"+l.get(i),l);
        }else{
            operator(i+1,0,prod*l.get(i),mid,exp+"*"+l.get(i),l);
        }
        operator(i+1,-1,0,mid+prod-l.get(i),exp+"-"+l.get(i),l);
        operator(i+1,1,0,mid+prod+l.get(i),exp+"+"+l.get(i),l);
    }
    public void rec(int in,List<Long>l){
        if(in==s.length()){
            operator(1,1,0,l.get(0),l.get(0)+"",l);
            return;
        }
        if(s.charAt(in)=='0'){
            l.add(0L);
            rec(in+1,l);
            l.remove(l.size()-1);
        }else{
            for(int i=in;i<s.length();i++){
                l.add(Long.parseLong(s.substring(in,i+1)));
                rec(i+1,l);
                l.remove(l.size()-1);
            }
        }
    }
    public List<String> addOperators(String num, int target) {
        result=new ArrayList<>();
        this.s=num;
        this.target=target;
        rec(0,new ArrayList<>(30));
        return result;
    }
}
class Solution {
public:
    vector<string> res;
    string s;
    int target, n;
    void solve(int it, string path, long long resSoFar, long long prev){
        if(it == n){
            if(resSoFar == target) res.push_back(path);
            return;
        }
        long long num = 0;
        string tmp;

        for(auto j = it; j < n; j++){
            if(j > it && s[it] == '0') break;

            num = num * 10 + (s[j] - '0');
            tmp.push_back(s[j]);

            if(it == 0) solve(j + 1, tmp, num, num);
            else{
                solve(j + 1, path + "+" + tmp, resSoFar + num, num);
                solve(j + 1, path + '-' + tmp, resSoFar - num, -num);
                solve(j + 1, path + '*' + tmp, resSoFar - prev + prev * num, prev * num);
            }
        }

    }
    vector<string> addOperators(string num, int target) {
        this -> target = target;
        s = num, n = num.size();

        solve(0, "", 0, 0);
        return res;
    }
};
var addOperators = function(num, target) {
    let res = [];

    let i = 0;

    const helper = (idx, sum, prev, path) => {
        if(idx >= num.length) {
            if(sum === target) {
                res.push(path);
            }
            return null;
        }

        for(let j = idx; j < num.length; j++) {

            if(j !== idx && num[idx] === "0")
                break;

            let n = Number(num.slice(idx, j+1));

            if(idx === 0) {
                helper(j + 1, sum + n, sum + n, path + n);
            } else {
                helper(j + 1, sum + n, n, path + "+" + n);

                helper(j + 1, sum - n, 0 - n, path + "-" + n);

                helper(j + 1, sum - prev + (prev * n), prev * n, path + "*" + n);
            }
        }

    }

    helper(i, 0, 0, "");

    return res;
};
Expression Add Operators