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

class Solution {
public:
    // Function that generates all valid expressions that evaluate to target
    vector<string> addOperators(string s, int target) {
        // This will store all expressions that match the target
        vector<string> result;

        // If input string is empty, return empty list
        if (s.empty()) return result;

        // Expression builder
        string path;

        // Start backtracking from position 0
        backtrack(s, target, 0, path, result);
        return result;
    }

private:
    // Backtracking helper that builds expressions
    void backtrack(const string &num, long long target, int pos,
                   string &expr, vector<string> &result) {

        // Get total length of the numeric string
        int n = num.size();

        // If we've reached the end of the string, evaluate the expression
        if (pos == n) {
            // If evaluation matches target, store expression
            if (evaluate(expr) == target) {
                result.push_back(expr);
            }
            return;
        }

        // Try every possible number starting from pos
        for (int end = pos; end < n; ++end) {

            // Skip numbers with leading zero
            if (end > pos && num[pos] == '0') break;

            // Extract substring (current number part)
            string part = num.substr(pos, end - pos + 1);

            // If at first position, we add the number without an operator
            if (pos == 0) {
                // Append part to expression
                expr.append(part);

                // Continue building next pieces
                backtrack(num, target, end + 1, expr, result);

                // Undo (remove part)
                expr.erase(expr.size() - part.size());
            } else {
                // Try adding '+'
                expr.push_back('+');
                expr.append(part);
                backtrack(num, target, end + 1, expr, result);
                expr.erase(expr.size() - part.size() - 1);

                // Try '-'
                expr.push_back('-');
                expr.append(part);
                backtrack(num, target, end + 1, expr, result);
                expr.erase(expr.size() - part.size() - 1);

                // Try '*'
                expr.push_back('*');
                expr.append(part);
                b