Expression Add Operators

Use DFS backtracking over every possible cut of the digit string, then try adding "+", "-", or "" before each next operand. The key detail is carrying both the running total and the last multiplied term so you can fix precedence when you place " ". That avoids rebuilding or re-parsing each expression and cleanly handles cases like "1+2 3" versus "1 2+3" while skipping operands with leading zeros.

Problem Statement

You are given a digit string num and an integer target. Your job is to insert binary operators "+", "-", and "*" between selected digits so the final expression evaluates exactly to target. Digits must stay in their original order, and each chosen operand may use one digit or multiple consecutive digits.

The tricky part is that you are not limited to single-digit operands, so every recursive step must consider splits like "1|23" and "12|3". At the same time, you must reject operands with leading zeros such as "05", and you must evaluate multiplication with proper precedence without using parentheses.

Examples

Example 1

Input: num = "123", target = 6

Output: ["1*2*3","1+2+3"]

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"]

Both "2 3+2" and "2+3 2" evaluate to 8.

Example 3

Input: num = "3456237490", target = 9191

Output: []

There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints

• 1 <= num.length <= 10
• num consists of only digits.
• -231 <= target <= 231 - 1

Solution Approach

Backtrack over every operand boundary

Start from the left side of num and choose the next operand by extending the current slice one digit at a time. This is the core search tree for Expression Add Operators: every position can either end the current number or keep growing it, which is why the interview hint about multi-digit numbers matters so much.

Carry running total and previous operand

For the first operand, place it directly with no operator. For later operands, recurse three ways: add it, subtract it, or multiply it. To support "*" correctly, store the last signed operand used in the running expression. When you multiply, remove that previous contribution from the total and replace it with previousOperand * currentOperand.

Prune leading-zero branches immediately

If a candidate operand starts with '0' and has more than one digit, stop extending that branch right away. This pruning is specific to this problem and cuts many invalid expressions early. It also prevents wrong outputs like "1+05" that may numerically work but violate the operand format rule.

Complexity Analysis

Metric	Value
Time	* At every step along the way, we consider exactly 4 different choices or 4 different recursive paths
Space	* For both Python and Java implementations we have a list data structure that we update on the fly and only for valid expressions do we create a new string and add to our answers array

The search explores many ways to split the string and place operators, so the time is exponential in num.length, commonly described as about O(4^n) in the worst case because each step can branch into extend, add, subtract, or multiply style choices. The extra space is O(n) for the recursion path and expression builder, excluding the output list. Since num.length is at most 10, the intended solution is exhaustive backtracking with tight pruning rather than dynamic programming.

What Interviewers Usually Probe

• They emphasize that a number can contain multiple digits, which is a hint to iterate over every substring as the next operand.
• They ask how to handle multiplication without evaluating the whole string each time, which points to tracking the previous operand.
• They mention leading zeros or bring up inputs like "105", which is a signal that pruning invalid operands matters.

Common Pitfalls or Variants

Common pitfalls

• Treating every digit as a separate operand and missing valid expressions such as "12-3".
• Evaluating left to right and getting multiplication wrong because "*" must adjust the previous term, not just append to the total.
• Allowing operands like "00" or "05", which creates invalid expressions even when the arithmetic matches target.

Follow-up variants

• Return only the count of valid expressions instead of the full list, which keeps the same backtracking structure but changes output handling.
• Allow division or parentheses, which breaks the simple previous-operand trick and requires a different expression-state model.
• Restrict operators to only "+" and "-", which removes precedence handling and makes state management much simpler.

FAQ

What is the main pattern behind Expression Add Operators?

The main pattern is backtracking search with pruning. You try every possible next operand boundary, then branch with "+", "-", and "*" while carrying enough state to evaluate the expression incrementally.

Why do we track the previous operand in LeetCode 282?

You need the previous operand to repair the running total when you place a multiplication operator. For example, after building "1+2", adding "3" should change the total from 3 to 1 + 2 3, so you subtract the old 2 contribution and add 6.

Why are leading zeros a special case here?

This problem allows multi-digit operands, but not ones with leading zeros. That means "0" is valid, while "05" and "00" as extended operands are not, so the DFS must stop extending as soon as a number starts with zero and grows past one digit.

Can Expression Add Operators be solved with dynamic programming instead of backtracking?

Backtracking is the standard fit because you must output every valid expression string, not just decide feasibility. The branching depends on exact expression text and multiplication history, so DFS with pruning is more direct than trying to memoize every partial state.

Why does the worst-case runtime grow so quickly?

At each position, you can keep extending the current operand or commit it and try different operators before the next operand. Because the algorithm enumerates many expression forms built from the digit string, the number of recursive branches grows exponentially with the length of num.