Abstract / Summary

Generate all possible expressions by adding operators between numbers in a string to see if any evaluate to a target value.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 44% (700k+ submissions).

Typical patterns to solve this problem:

• Backtracking
• Math
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method addOperators. The method receives a numeric string num and an integer target. It returns a list of all possible expressions that can be built by inserting the binary operators +, -, or * between the digits of num such that the expression evaluates exactly to target. The core of the algorithm is a depth-first search that constructs candidate formulas character by character and evaluates them only when a complete formula has been assembled.

Core Recursive Exploration

The heart of the solution is the nested function deeper. It is invoked with three arguments: the current position in the input string, the partially built formula, and a flag indicating whether the most recent digit was a leading zero. The function proceeds as follows.

def deeper(pos, formula, leadingZero):
    if pos == len(num):
        if eval(formula) == target:
            result.append(formula)
        return

When the recursion reaches the end of the input (pos == len(num)), the accumulated formula is evaluated with Python’s built-in eval. If the computed value matches target, the formula is stored in the result list. This termination clause guarantees that only complete expressions are considered for inclusion.

Extending the Formula

If the end has not been reached, the next digit is extracted:

digit = num[pos]

The algorithm then explores four possibilities for extending the current formula:

1. Concatenation without an operator - allowed only when the previous digit was not a leading zero. This prevents the creation of numbers such as "05".

if not leadingZero:
    deeper(pos + 1, formula + digit, False)

2. Insertion of a plus sign - always permissible. The leadingZero flag for the new segment is set based on whether the digit being added is '0'.

deeper(pos + 1, formula + "+" + digit, digit == "0")

3. Insertion of a minus sign - analogous to the plus case.

deeper(pos + 1, formula + "-" + digit, digit == "0")

4. Insertion of a multiplication sign - also analogous.

deeper(pos + 1, formula + "*" + digit, digit == "0")

Each recursive call advances the position by one, appends the appropriate operator and digit to the formula, and updates the leadingZero flag to reflect the start of a new numeric token.

Initiation and Result Collection

The recursion is seeded with the first digit of num as the initial formula. The leadingZero flag is set according to whether that first digit is '0'.

deeper(1, num[0], num[0] == "0")
return result

The final list result contains all valid expressions that meet the target criterion.

Edge Cases Handled

The implementation explicitly guards against the formation of numbers with leading zeros. The leadingZero flag is propagated through recursive calls and prevents concatenation when the current token would start with '0'. This ensures that expressions such as "1+05" are never generated, aligning with typical numeric parsing rules.

When the input string consists of a single digit, the recursion starts at position 1, which immediately satisfies the termination condition. The sole digit is evaluated directly against target, and the correct result (either an empty list or a list containing the digit) is produced without any operator insertion.

If the input contains consecutive zeros, the flag logic (digit == "0") correctly treats each zero as a potential start of a new token, allowing expressions like "0+0" while still prohibiting illegal concatenations like "00".

Implicit Performance Optimizations

The algorithm avoids repeated evaluation of partial expressions by postponing the call to eval until a full formula is constructed. This reduces the overhead associated with interpreting incomplete arithmetic strings.

String concatenation is performed incrementally, reusing the existing formula and appending only a single character or operator at each step. This approach minimizes the creation of intermediate strings compared to rebuilding the entire expression from scratch at each recursion level.

The leadingZero flag serves a dual purpose: it enforces syntactic correctness and also prunes the search space early. By skipping concatenation branches that would produce invalid numbers, the recursion explores fewer paths, leading to a more efficient traversal of the combinatorial space of operator placements.

Overall, the design balances simplicity with targeted pruning, delivering a solution that systematically enumerates valid expressions while keeping unnecessary work to a minimum.

Imagine a long train track made of different number cards. The goal is to figure out how to put little plus, minus, and times signs between these numbers so that when you finish the math, the total matches a special target number.

Think of the computer as someone playing a game of hide and seek with numbers. It starts at the very beginning of the string of numbers and tries every possible combination. At each step, it has to decide whether to add, subtract, or multiply the next number. It also looks to see if it just started a brand new number or if it is continuing one it already began.

Because the computer is very fast, it explores all these different paths like a tiny ant running along many branches. Every time it reaches the very end of the line of numbers, it stops to do the math. If the math adds up to the target number, it puts that specific sequence in a basket to remember it for later. Once it has looked at every single path and every possible sign, the basket will be full of all the correct ways to reach the goal.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: exponential
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java			Python			TS
	WalkCCC	C++	Java			Python
	leetcode.ca		Java			Python	C#
	LeetcodeHelp	C++	Java			Python
	MemoryLimitExceeded	C++				Python
	Progiez	C++	Java			Python
github	aylei			Rust
	black-shadows	C++
	charles-wangkai		Java
	chenyanzhe	C++
	everthis				JS
	fengvyi	C++
	gouthampradhan		Java
	haoel	C++
	JoshCrozier				JS
	keineahnung2345	C++
	linouk23	C++
	lkwq007					Python
	qiyuangong	C++
	ruoru			Rust
	suxrobGM						C#
	varunu28		Java
	vli02							C
	wisdompeak	C++
	XiaotaoGuo	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C#, Java, Python
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
aylei	Rust
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fengvyi	C++
gouthampradhan	Java
haoel	C++
JoshCrozier	JavaScript
keineahnung2345	C++
linouk23	C++
lkwq007	Python
qiyuangong	C++
ruoru	Rust
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality