Expression Add Operators: Backtracking with Precedence

def addOperators(num, target):
    result = []
    n = len(num)

    def bt(idx, path, eval_val, last):
        if idx == n:
            if eval_val == target:
                result.append(path)
            return
        for i in range(idx, n):
            s = num[idx:i+1]
            # No leading zeros (except "0" itself)
            if len(s) > 1 and s[0] == '0': break
            val = int(s)
            if idx == 0:
                # First number, no operator
                bt(i+1, s, val, val)
            else:
                bt(i+1, path+'+'+s, eval_val+val, val)
                bt(i+1, path+'-'+s, eval_val-val, -val)
                # Multiplication: undo last add, redo with mult
                bt(i+1, path+'*'+s, eval_val-last+last*val, last*val)

    bt(0, '', 0, 0)
    return result

print(addOperators("123", 6))   # ['1+2+3', '1*2*3']
print(addOperators("232", 8))   # ['2*3+2', '2+3*2']

#include <bits/stdc++.h>
using namespace std;

vector<string> addOperators(string num, int target) {
    vector<string> result;
    int n = num.size();
    function<void(int, string, long long, long long)> bt = [&](int idx, string path, long long eval, long long last) {
        if (idx == n) {
            if (eval == target) result.push_back(path);
            return;
        }
        for (int i = idx; i < n; i++) {
            string s = num.substr(idx, i-idx+1);
            if (s.size() > 1 && s[0] == '0') break; // no leading zeros
            long long val = stoll(s);
            if (idx == 0) {
                bt(i+1, s, val, val);
            } else {
                bt(i+1, path+"+"+s, eval+val, val);
                bt(i+1, path+"-"+s, eval-val, -val);
                bt(i+1, path+"*"+s, eval-last+last*val, last*val);
            }
        }
    };
    bt(0, "", 0, 0);
    return result;
}

import java.util.*;

public class AddOperators {
    public List<String> addOperators(String num, int target) {
        List<String> result = new ArrayList<>();
        backtrack(num, target, 0, "", 0L, 0L, result);
        return result;
    }

    void backtrack(String num, long target, int idx, String path, long eval, long last, List<String> result) {
        if (idx == num.length()) {
            if (eval == target) result.add(path);
            return;
        }
        for (int i = idx; i < num.length(); i++) {
            String s = num.substring(idx, i+1);
            if (s.length() > 1 && s.charAt(0) == '0') break;
            long val = Long.parseLong(s);
            if (idx == 0) {
                backtrack(num, target, i+1, s, val, val, result);
            } else {
                backtrack(num, target, i+1, path+"+"+s, eval+val, val, result);
                backtrack(num, target, i+1, path+"-"+s, eval-val, -val, result);
                backtrack(num, target, i+1, path+"*"+s, eval-last+last*val, last*val, result);
            }
        }
    }
}