Expression Add Operators — Hard Problem & Solution

Problem statement

num is a string of digits. Between any two neighbouring digits you may insert one of the binary operators +, - or *, or nothing (which glues the digits into a longer number). The digits stay in their order.

Return every expression built this way whose value equals target, evaluated with the usual precedence (* before + and -, left to right otherwise). An operand may not have a leading zero: 0 on its own is fine, but 05 is not.

List the expressions in ascending ASCII order (so * < + < - < digits). Return an empty list if none works.

Example 1

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]

Example 2

Input: num = "105", target = 5
Output: ["1*0+5","10-5"]
Explanation: `1*05` is not allowed: `05` has a leading zero.

Example 3

Input: num = "99", target = 10
Output: []

Constraints

• 1 <= num.length <= 10
• num consists only of digits
• -2^31 <= target <= 2^31 - 1

How to solve Expression Add Operators

Backtrack over operand boundaries and operators while evaluating on the fly. The only tricky operator is *, which binds tighter than what was already added — remembering the last term lets us replace it in O(1).

Approach

1. dfs(pos, expr, value, last): if pos == n, record expr when value == target.
2. For every end i >= pos, let cur be the number num[pos..i]; stop as soon as the operand would start with a 0 and have two or more digits.
3. At pos == 0, the operand starts the expression: recurse with value = last = cur.
4. Otherwise recurse three times: + (value + cur, last cur), - (value - cur, last -cur), * (value - last + last * cur, last last * cur).
5. Sort the collected expressions.

Why it works

Under standard precedence an expression is a sum of signed products. last is the signed product currently being built; extending it by * cur changes the total by replacing last with last * cur, which is exactly the update. Every expression corresponds to one sequence of operand ends and operators, so each is generated once.

Complexity

• Time — O(4^n · n)
• Space — O(n) recursion depth besides the output

Pitfalls

• Operands and intermediate products can exceed 32 bits ("9999999999"); use 64-bit integers.
• Leading zeros: 0 alone is a valid operand, but nothing may be glued after a leading 0.
• Keep the sign in last for subtraction, or a - b * c evaluates wrongly.

Reference solution

Python

from typing import List

def addOperators(num: str, target: int) -> List[str]:
    n = len(num)
    out = []

    def dfs(pos, expr, value, last):
        if pos == n:
            if value == target:
                out.append(expr)
            return
        for i in range(pos, n):
            if i > pos and num[pos] == '0':
                break
            part = num[pos:i + 1]
            cur = int(part)
            if pos == 0:
                dfs(i + 1, part, cur, cur)
            else:
                dfs(i + 1, expr + '+' + part, value + cur, cur)
                dfs(i + 1, expr + '-' + part, value - cur, -cur)
                dfs(i + 1, expr + '*' + part, value - last + last * cur, last * cur)

    dfs(0, '', 0, 0)
    out.sort()
    return out

JavaScript

var addOperators = function(num, target) {
    var n = num.length;
    var out = [];
    var dfs = function(pos, expr, value, last) {
        if (pos === n) {
            if (value === target) out.push(expr);
            return;
        }
        for (var i = pos; i < n; i++) {
            if (i > pos && num.charAt(pos) === '0') break;
            var part = num.substring(pos, i + 1);
            var cur = parseInt(part, 10);
            if (pos === 0) {
                dfs(i + 1, part, cur, cur);
            } else {
                dfs(i + 1, expr + '+' + part, value + cur, cur);
                dfs(i + 1, expr + '-' + part, value - cur, -cur);
                dfs(i + 1, expr + '*' + part, value - last + last * cur, last * cur);
            }
        }
    };
    dfs(0, '', 0, 0);
    out.sort();
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Number of Squareful Arrays Hard
• Permutation Sequence Hard
• 24 Game Hard
• Verbal Arithmetic Puzzle Hard
• Transform to Chessboard Hard
• Stone Game V Hard