In this article, we will explore how to generate a valid mathematical expression from a string of digits that evaluates to a given target number using Java. This type of problem is common in coding interviews and algorithm challenges, as it involves recursive thinking, backtracking, and careful handling of operator precedence. We will walk through the core logic, discuss the key concepts behind the approach, and present a Java implementation that tries all possible ways to insert the +, -, and * operators between digits.
1. Problem Description
Given a string containing only digits (e.g., "123") and a target value (e.g., 6), insert the binary operators +, -, or * between the digits so that the resulting mathematical expression evaluates to the target value. You are not allowed to reorder digits or insert parentheses. All valid combinations should be returned as a list of strings.
1.1 Key Concepts and Approach
This problem is best solved using a backtracking algorithm, which systematically explores all possible combinations of operators inserted between digits. Backtracking is a recursive technique that tries out different choices at each step and backtracks when a choice doesn’t lead to a valid solution. In this context, it tries every possible operator (+, -, *) between all splits of the numeric string, tracking the current expression, its evaluated result, and the last operand to correctly handle multiplication precedence.
The algorithm avoids invalid cases like numbers with leading zeros and only adds an expression to the final result if it consumes the entire input string and the evaluation equals the target. By pruning paths early when conditions fail (like leading zeros), backtracking keeps the solution efficient and avoids unnecessary computation.
2. Java Implementation
To tackle this problem, we implement a recursive backtracking solution in Java that explores all possible ways to insert +, -, and * operators between the digits of the input string. Below is the Java code that solves the problem and returns all valid expressions that evaluate to the given target.
import java.util.ArrayList;
import java.util.List;
public class ValidExpressionEvaluator {
public List<String> addOperators(String num, int target) {
List<String> result = new ArrayList<>();
if (num == null || num.length() == 0) return result;
backtrack(result, "", num, target, 0, 0, 0);
return result;
}
private void backtrack(List<String> result, String path, String num, int target, int pos, long eval, long prevNum) {
if (pos == num.length()) {
if (eval == target) {
result.add(path);
}
return;
}
for (int i = pos; i < num.length(); i++) {
// Avoid numbers with leading zero
if (i != pos && num.charAt(pos) == '0') break;
String currentStr = num.substring(pos, i + 1);
long currentNum = Long.parseLong(currentStr);
if (pos == 0) {
// First number, no operator before it
backtrack(result, currentStr, num, target, i + 1, currentNum, currentNum);
} else {
backtrack(result, path + "+" + currentStr, num, target, i + 1, eval + currentNum, currentNum);
backtrack(result, path + "-" + currentStr, num, target, i + 1, eval - currentNum, -currentNum);
backtrack(result, path + "*" + currentStr, num, target, i + 1,
eval - prevNum + prevNum * currentNum, prevNum * currentNum);
}
}
}
public static void main(String[] args) {
ValidExpressionEvaluator solver = new ValidExpressionEvaluator();
String input = "123";
int target = 6;
List<String< expressions = solver.addOperators(input, target);
System.out.println("Expressions that evaluate to " + target + ":");
for (String expr : expressions) {
System.out.println(expr);
}
}
We start by calling the addOperators method with the input string and the target value. The backtrack method does the main work. At each index, we try to split the string into a number, convert it to long, and recursively try to add it to the current expression using +, -, or *.
- The
evalvariable holds the current total value of the expression. - The
prevNumhelps in handling multiplication. For example, in2+3*2, we first get2+3 = 5and then need to backtrack and apply multiplication:2 + (3*2) = 8.
We also handle the case of numbers with leading zeros (like "05") by skipping them unless the number is just "0".
Sample Output
When running the above code with input = "123" and target = 6, the output is:
Expressions that evaluate to 6: 1+2+3 1*2*3
Explanation: The expression "1+2+3" evaluates to 6, as does "1*2*3", so both are included in the final output. These expressions correctly use the given digits and operators to reach the target value. Other combinations such as "12+3", "1+23", or "1*23" result in values different from 6 and are therefore excluded from the output. Only expressions that evaluate exactly to the target number are considered valid and returned.
3. Another Example
If you change the input to "105" and the target to 5, you get:
Expressions that evaluate to 5: 1*0+5 10-5
The expression "1*0+5" evaluates as 1 * 0 + 5, which simplifies to 0 + 5 = 5, matching the target value. Similarly, "10-5" evaluates to 5 as well, so both are included in the final output. However, an expression like "1*05" is considered invalid because "05" is not a valid number as it contains a leading zero, which violates the standard numerical format. The algorithm correctly handles such cases by skipping over any substrings with leading zeros, ensuring that only valid and properly formatted expressions are included in the results.
4. Conclusion
In this article, we implemented a Java solution to generate valid expressions from a string of digits that evaluate to a target value. Using a recursive backtracking approach, we examined all possible operator insertions while addressing important cases such as leading zeros and operator precedence. The final solution efficiently identifies and returns all expressions that correctly match the target.
5. Download the Source Code
This article covered generating a valid expression from a string of numbers in Java to match a target value.
You can download the full source code of this example here: Java valid expression string numbers
