Problem Statement
The task is to generate all possible expressions by inserting the binary operators '+' (addition), '-' (subtraction), and '*' (multiplication) between the digits of a given numeric string num. These expressions, when evaluated, should result in a value equal to the specified target integer. It's crucial that these generated numeric expressions do not begin with any zeros unless the zero itself is the only digit, adhering to standard numeric representations.
Examples
Example 1
Input:
num = "123", target = 6
Output:
["1*2*3","1+2+3"]
Explanation:
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"]
Explanation:
Both "2*3+2" and "2+3*2" evaluate to 8.
Example 3
Input:
num = "3456237490", target = 9191
Output:
[]
Explanation:
There are no expressions that can be created from "3456237490" to evaluate to 9191.
Constraints
1 <= num.length <= 10numconsists of only digits.-231 <= target <= 231 - 1
Approach and Intuition
To solve this problem, we can use a recursive approach with backtracking to explore all possible ways to insert the operators:
- Initialization: Start with an empty expression and the first character of
num. Progressively add each character to the expression. - Recursive Exploration:
- At every digit in
num, decide whether to:- Insert a '+' and recursively process the remaining characters.
- Insert a '-' and recursively process the remaining characters.
- Insert a '*' to perform multiplication and recursively process the remaining characters.
- Simply extend the current numeric value by appending the next digit (carefully considering not to start any new number with zero unless it's the only digit).
- At every digit in
- Evaluation and Backtracking:
- Constantly evaluate the expression as we extend it.
- If at any point the partial expression matches the target (when all characters have been processed), add it to the result list.
- If an expression doesn't work out, backtrack to explore the next possible set of operations.
- Base and Edge Cases:
- If
numstarts with '0', only '0' can be used before an operator must be inserted (to avoid leading zeros in any number). - Continuously handle calculations that might involve large numbers or potential integer overflows, especially with multiple multiplications.
- If
The use of recursive backtracking is efficient here due to the constraint that the length of num is at most 10, but being cautious with calculations is critical because of the possibility of large integer values and the significant variations in expressions that can be formed. This approach ensures all potential expressions are considered, and those meeting the target requirement are captured.
Solutions
- Java
- Python
class Solution {
public ArrayList<String> results;
public String numberSequence;
public long goal;
public void search(
int pos, long prevOperand, long currOperand, long accumulated, ArrayList<String> operations) {
String digits = this.numberSequence;
// Processing completion check
if (pos == digits.length()) {
// Check if current total equals goal and no pending operations
if (accumulated == this.goal && currOperand == 0) {
StringBuilder expression = new StringBuilder();
operations.subList(1, operations.size()).forEach(v -> expression.append(v));
this.results.add(expression.toString());
}
return;
}
// Append current digit to operand
currOperand = currOperand * 10 + Character.getNumericValue(digits.charAt(pos));
String currValStr = Long.toString(currOperand);
// Skip invalid leading zero cases
if (currOperand > 0) {
// Continue without adding operators
search(pos + 1, prevOperand, currOperand, accumulated, operations);
}
// Addition operation
operations.add("+");
operations.add(currValStr);
search(pos + 1, currOperand, 0, accumulated + currOperand, operations);
operations.remove(operations.size() - 1);
operations.remove(operations.size() - 1);
if (operations.size() > 0) {
// Subtraction operation
operations.add("-");
operations.add(currValStr);
search(pos + 1, -currOperand, 0, accumulated - currOperand, operations);
operations.remove(operations.size() - 1);
operations.remove(operations.size() - 1);
// Multiplication operation
operations.add("*");
operations.add(currValStr);
search(
pos + 1,
currOperand * prevOperand,
0,
accumulated - prevOperand + (currOperand * prevOperand),
operations);
operations.remove(operations.size() - 1);
operations.remove(operations.size() - 1);
}
}
public List<String> addOperators(String num, int target) {
if (num.length() == 0) {
return new ArrayList<String>();
}
this.goal = target;
this.numberSequence = num;
this.results = new ArrayList<String>();
this.search(0, 0, 0, 0, new ArrayList<String>());
return this.results;
}
}
The provided Java code defines a solution for the problem where one needs to insert mathematical operators ('+', '-', '*') into a string of digits to form valid arithmetic expressions that evaluate to a given target number.
The
Solutionclass has several properties:resultsto store valid expression strings.numberSequenceto store the input number as a string.goalto store the target value.
The
searchmethod is a recursive function designed to try placing each of the mathematical operators or continuing without any operator between the digits:- It terminates the recursion when it reaches the end of the string (
pos == digits.length()). If the current expression evaluates exactly to the goal without any pending calculations (currOperand == 0), it joins the components into a complete expression and adds it toresults. - It handles numbers carefully to avoid expressions with leading zeros unless the number is zero itself.
- It explores three possible paths by recursively calling itself:
- Continuing the current operand by appending a digit.
- Trying addition, subtraction, and multiplication with the current operand.
- It terminates the recursion when it reaches the end of the string (
Error handling for expressions starting with zeros and handling of the precedence in operations, particularly with multiplication, are managed using the accumulated value and keeping track of the previous operand.
The
addOperatorsmethod initializes the recursion:- It checks if the input number is empty.
- Sets the
goalandnumberSequence. - Starts the recursive
searchfrom the beginning of the string.
Usage:
- Construct an instance of
Solution. - Invoke
addOperatorswith a num string and a target integer to get a list of all valid expressions that result in the target.
- Construct an instance of
This solution effectively constructs expressions using backtracking, ensuring that all possible combinations of operators are considered and processed efficiently.
class Solution:
def evaluate_expression(self, digits: 'str', goal: 'int') -> 'List[str]':
length = len(digits)
results = []
def backtrack(pos, previous, current, total, seq):
# Processing finishes when end of string is reached
if pos == length:
# Check if the expression evaluates to goal
if total == goal and current == 0:
results.append("".join(seq[1:])) # skip the initial operator
return
# Build the current operand from the string
current = current * 10 + int(digits[pos])
operand_str = str(current)
# Ignore leading zeros
if current > 0:
# Continue with building the number
backtrack(pos + 1, previous, current, total, seq)
# Addition
seq.append('+')
seq.append(operand_str)
backtrack(pos + 1, current, 0, total + current, seq)
seq.pop()
seq.pop()
# Only add subtraction and multiplication if there are operands formed before
if seq:
# Subtraction
seq.append('-')
seq.append(operand_str)
backtrack(pos + 1, -current, 0, total - current, seq)
seq.pop()
seq.pop()
# Multiplication
seq.append('*')
seq.append(operand_str)
new_value = previous * current
backtrack(pos + 1, new_value, 0, total - previous + new_value, seq)
seq.pop()
seq.pop()
backtrack(0, 0, 0, 0, [])
return results
This Python solution introduces a method to add operators ('+', '-', '*') between the digits of a string such that the expression equates to a specific target number. Here's a summary of how this solution works:
- Define a class
Solutioncontaining the methodevaluate_expressionwhich takes two parameters: a string of digits and a goal integer. - Initialize an empty list called
resultsto store valid expressions. - Define a nested function
backtrackto handle the recursive construction of possible expressions. It takes parameters: the current position in the string (pos), the value of the last operand (previous), the current operand being built (current), the running total of the current expression (total), and the current sequence of characters (seq). - In
backtrack, handle sequence termination when the end of the digits string is reached. - If the current built-up expression totaling to
totalequalsgoal, append the expression toresults. - Recurse to form the current operand by extending it with the next digit to handle potential multi-digit operands.
- Add the expression-separating operators only if there's no leading zero in the current number or if it's not the beginning of the sequence.
- Explore three possible recursive paths from each position — one each for addition, subtraction, and multiplication — updating the sequence and total accordingly.
- Start the backtracking process with base values for total, current, and previous operands.
Run the recursive backtrack function initially from position 0 of the string and with base values set to reflect an empty initial state, eventually returning the list of all valid combinations that meet the target expression's value. This approach ensures that all combinations of numbers and operators leading up to the target are considered.
No comments yet.