☕ DSA Java Articles

Topics › Recursion and Backtracking › Trying out all Combos / Hard

Expression Add Operators

Hard TUF ID 3 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given a string num containing only digits and an integer target. Between any two adjacent digits you may insert one of the binary operators +, - or *, or insert nothing, in which case the digits join into a longer operand. Return all expressions that evaluate to target, in any order. Operands must not have leading zeros: "05" is not allowed, "0" on its own is. The expression follows normal precedence, so * binds tighter than + and -. No unary minus is allowed.

Constraints: 1 ≤ num.length ≤ 10, -2^31 ≤ target ≤ 2^31 - 1.

Example 1

num = "123", target = 6
answer = ["1+2+3", "1*2*3"]

Example 2

num = "105", target = 5
answer = ["1*0+5", "10-5"]        // "1*05" is rejected because 05 has a leading zero

Example 3

num = "00", target = 0
answer = ["0+0", "0-0", "0*0"]    // "00" is not a valid operand

Approach 1: Brute force, generate every string and evaluate it

Intuition. Between each pair of adjacent digits there are exactly four choices ("", +, -, *), so there are 4^(n-1) candidate expressions. Build each one as a string, throw away those with a leading-zero operand, evaluate the rest with a small precedence-aware evaluator, and keep the ones that hit target. It is slow but conceptually simple, and the evaluator doubles as a specification for the faster method.

The evaluator keeps three numbers: total (sum of finished terms), term (the product currently being built) and cur (the operand being read). On + or -, the current term is complete and is added to total, and the new operand starts a new term with the right sign. On *, the operand multiplies into the current term instead. A virtual trailing + flushes the last operand.

Algorithm.

  1. Start the expression with num[0] and recurse on index 1.
  2. At index i, try each of the four separators followed by num[i], recurse, then truncate the builder back (setLength).
  3. At the end, if no operand has a leading zero and evaluate(expr) == target, record it.
static List<String> bruteForce(String num, int target) {
    List<String> result = new ArrayList<>();
    if (num.isEmpty()) return result;
    buildAll(num, 1, new StringBuilder().append(num.charAt(0)), target, result);
    return result;
}

private static void buildAll(String num, int i, StringBuilder expr, int target, List<String> result) {
    if (i == num.length()) {
        if (hasNoLeadingZero(expr) && evaluate(expr) == target) result.add(expr.toString());
        return;
    }
    char digit = num.charAt(i);
    int len = expr.length();
    for (String op : new String[]{"", "+", "-", "*"}) {
        expr.append(op).append(digit);
        buildAll(num, i + 1, expr, target, result);
        expr.setLength(len);                         // undo
    }
}

/** Evaluates digits joined by +, - and * with the usual precedence: a running total of finished terms plus the current product term. */
private static long evaluate(CharSequence expr) {
    long total = 0, term = 0, cur = 0;
    char pending = '+';
    for (int i = 0; i <= expr.length(); i++) {
        char ch = i < expr.length() ? expr.charAt(i) : '+';   // a final '+' flushes the last operand
        if (Character.isDigit(ch)) {
            cur = cur * 10 + (ch - '0');
            continue;
        }
        if (pending == '*') {
            term *= cur;
        } else {
            total += term;
            term = pending == '+' ? cur : -cur;
        }
        pending = ch;
        cur = 0;
    }
    return total + term;
}

hasNoLeadingZero walks the operands and rejects any that has more than one digit and starts with 0.

Complexity. Time O(4^(n-1) · n): every candidate string is built and scanned; for n = 10 that is 262 144 strings of up to 19 characters, fast enough but wasteful. Space O(n) for the builder and recursion, excluding the output.

Approach 2: Optimal, evaluate while backtracking

Intuition. Two improvements fall out of looking at the brute force more closely.

First, instead of deciding digit by digit, decide operand by operand: at position pos, the next operand is num[pos..end] for some end, and the leading-zero rule becomes a one-line prune (if num[pos] == '0', the operand is just "0", so stop extending after end == pos).

Second, evaluating at the leaf repeats work done by every sibling. Carry the evaluation along the recursion with two numbers:

Appending + x gives value + x with last = x. Appending - x gives value - x with last = -x. Appending * x must undo the last term and replace it by its product: value - last + last * x, with last = last * x. This is exactly the total / term bookkeeping from the evaluator, moved into the recursion so that each node costs O(1). The expression text itself lives in a char[] buffer with a length index, so undo is implicit.

Algorithm.

  1. search(pos, len, value, last): if pos == n, record the buffer if value == target.
  2. For end from pos: stop if the operand would have a leading zero; extend operand by one digit.
  3. If pos == 0, copy the digits in and recurse with value = last = operand (no operator before the first operand).
  4. Otherwise copy the digits after an operator slot and recurse three times, writing +, -, * into the slot with the update rules above.
static List<String> optimal(String num, int target) {
    List<String> result = new ArrayList<>();
    if (num.isEmpty()) return result;
    char[] expr = new char[2 * num.length()];       // at most n digits and n - 1 operators
    search(num, 0, expr, 0, 0L, 0L, target, result);
    return result;
}

private static void search(String num, int pos, char[] expr, int len, long value, long last, int target, List<String> result) {
    if (pos == num.length()) {
        if (value == target) result.add(new String(expr, 0, len));
        return;
    }
    long operand = 0;
    for (int end = pos; end < num.length(); end++) {
        if (end > pos && num.charAt(pos) == '0') break;        // "0" is fine, "05" is not
        operand = operand * 10 + (num.charAt(end) - '0');
        int digits = end - pos + 1;
        if (pos == 0) {                                        // first operand: no operator in front of it
            num.getChars(pos, end + 1, expr, len);
            search(num, end + 1, expr, len + digits, operand, operand, target, result);
        } else {
            num.getChars(pos, end + 1, expr, len + 1);         // digits go after the operator slot
            expr[len] = '+';
            search(num, end + 1, expr, len + 1 + digits, value + operand, operand, target, result);
            expr[len] = '-';
            search(num, end + 1, expr, len + 1 + digits, value - operand, -operand, target, result);
            expr[len] = '*';
            search(num, end + 1, expr, len + 1 + digits, value - last + last * operand, last * operand, target, result);
        }
    }
}

Dry run on num = "232", target = 8:

expression so far value last next step
2 2 2 operand 3
2+3 5 3 operand 2: + gives 7, - gives 3, * gives 5 - 3 + 3·2 = 8 ✓ 2+3*2
2-3 -1 -3 + 1, - -3, * -1 + 3 + (-3)·2 = -4
2*3 6 6 + 8 ✓ 2*3+2, - 4, * 12
23 23 23 operand 2: 25, 21, 46
232 232 232 end: 232 ≠ 8

The * row for 2-3 shows why last carries its sign: the term being replaced is -3, so the product term is -6, and value - last correctly adds the 3 back before subtracting 6.

Complexity. Time O(4^(n-1)) nodes in the worst case (one for each way to cut the string and choose operators) with O(1) arithmetic per node; copying each accepted expression costs O(n). Space O(n) for the buffer and recursion, excluding the output. The leading-zero break also prunes whole subtrees that the brute force only rejects at the leaves.

Edge cases and pitfalls