Generate a Valid Expression From a String of Numbers to Get Target Number

1. Introduction

In this tutorial, we’ll explore how to solve the problem of generating all valid expressions by inserting binary operators between the digits of a string. The resulting expression must match the target number. This problem combines string manipulation, recursion, and backtracking concepts, making it a common interview question.

We’ll develop a solution using a backtracking algorithm. We’ll also review how the algorithm works recursively and test its functionality. Finally, we’ll look at the time and space complexity to ensure that our solution is efficient.

2. Understanding the Problem

Let’s start by breaking down the problem and its requirements. We have a string of digits and an integer target. We need to insert binary operators (+, -, or *) between the digits so that the resulting expression evaluates to the specified target value.

The given string is between one and ten digits long. Additionally, the target value falls within the range of a 32-bit signed integer. This implies handling numbers of varying lengths. We also need to ensure that our solution works efficiently within these bounds.

Furthermore, we can split the string into multiple substrings representing operands, which can’t contain leading zeros unless the operand is 0. For example, 05 or 012 are invalid, but zero is valid.

To conclude, the task is to explore all possible combinations of operands and insert the allowed operators to check which combinations match the target. If, for example, the string is “123” and the target value is 6, valid expressions could be 1*2*3 and 1+2+3, both of which evaluate to 6.

Let’s explore how to solve this efficiently using backtracking.

3. Backtracking Algorithm

In short, backtracking is a problem-solving technique that systematically explores all potential combinations to solve a computational problem. The algorithm narrows the possibilities by trying partial solutions and discarding those that fail to meet the problem’s constraints until it finds a valid solution.

In other words, it’s an enhanced brute-force method that solves problems recursively, making a sequence of decisions. The concept of backtracking suggests that if the current solution proves unsuitable, the algorithm discards it and backtracks to explore alternative solutions.

The backtracking approach is typically applied when there are multiple potential solutions to a problem. It’s often used in scenarios that require exploring all possible combinations or configurations, such as generating permutations, solving crosswords or Sudoku puzzles, tackling problems like the N-Queens and maze navigation, or evaluating mathematical expressions.

Let’s implement a recursive backtracking to demonstrate the described approach.

4. Recursive Backtracking Implementation

In brief, for the given problem, the backtracking algorithm recursively explores all possible ways to insert the operators (+, -, or *) between the digits. At each step, we decide on an operator to place between two digits and continue exploring the next part of the string. If the resulting expression matches the target at any point, we consider that combination a valid solution.

4.1. Evaluating Expressions

To begin, we must define an entry point. The process() method initializes a result list, wraps the input string and target value into an Equation object, and starts the recursive backtracking process by calling the evaluateExpressions() function:

List<String> process(String digits, int target) {
    final List<String> validExpressions = new ArrayList<>();
    evaluateExpressions(validExpressions, new Equation(digits, target), 0, new StringBuilder(), 0, 0);
    return validExpressions;
}

Next, within the evaluateExpressions() method, we distinguish the two cases – when all input string digits are processed, or the processing is still in progress. If we reach the end of the string, we check if the evaluated value matches the target. The current expression is considered valid and added to the result list if it does:

void evaluateExpressions(List<String> validExpressions, Equation equation,
  int index, StringBuilder currentExpression, long currentResult,
  long lastOperand) {

    if (allDigitsProcessed(equation.getDigits(), index)) {
        if (currentResult == equation.getTarget()) {
            validExpressions.add(currentExpression.toString());
        }
        return;
    }

    exploreExpressions(validExpressions, equation, index, currentExpression, currentResult, lastOperand);
}

On the other hand, the exploreExpressions() method iterates through the remaining digits and forms numbers incrementally. It recursively explores three possible branches for each number by inserting different operators, updating both the expression and its current value at each step:

void exploreExpressions(List<String> validExpressions, Equation equation,
  int index, StringBuilder currentExpression, long currentResult,
  long lastOperand) {

    for (int endIndex = index; endIndex < equation.getDigits().length(); endIndex++) {
        if (isWithLeadingZero(equation.getDigits(), index, endIndex)) {
            break;
        }

        long currentOperandValue = Long.parseLong(equation.getDigits()
          .substring(index, endIndex + 1));

        if (isFirstOperand(index)) {
            processFirstOperand(validExpressions, equation, endIndex, 
              currentExpression, currentOperandValue);
        } else {
            applyAddition(validExpressions, equation, endIndex, 
              currentExpression, currentResult, currentOperandValue);
            applySubtraction(validExpressions, equation, endIndex, 
              currentExpression, currentResult, currentOperandValue);
            applyMultiplication(validExpressions, equation, endIndex, 
              currentExpression, currentResult, currentOperandValue, lastOperand);
        }
    }
}

Let’s see how to handle the different arithmetic operations.

4.2. Processing Arithmetic Operations

Based on the operation, different methods are invoked. For example, applyAddition() appends the plus symbol and the current operand value to the current expression, updates the result by adding the current operand value, and recursively evaluates the next potential expression:

void applyAddition(List<String> validExpressions, Equation equation,
  int endIndex, StringBuilder currentExpression, long currentResult,
  long currentOperandValue) {
    appendToExpression(currentExpression, Operator.ADDITION, currentOperandValue);

    evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
      currentResult + currentOperandValue, currentOperandValue);

    removeFromExpression(currentExpression, Operator.ADDITION, currentOperandValue);
}

Afterward, it backtracks by removing the most recently added values and attempts the next possibility.

Similarly, the applySubtraction() method adds a minus symbol and operand value to the current expression and adjusts the result by subtracting the operand value. It then continues the recursive evaluation:

void applySubtraction(List<String> validExpressions, Equation equation,
  int endIndex, StringBuilder currentExpression, long currentResult,
  long currentOperandValue) {
    appendToExpression(currentExpression, Operator.SUBTRACTION, currentOperandValue);

    evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
      currentResult - currentOperandValue, -currentOperandValue);

    removeFromExpression(currentExpression, Operator.SUBTRACTION, currentOperandValue);
}

Finally, the applyMultiplication() method adjusts the result by considering the previously used operand. This ensures the correct order of operations:

void applyMultiplication(List<String> validExpressions, Equation equation,
  int endIndex, StringBuilder currentExpression, long currentResult,
  long currentOperandValue, long lastOperand) {
    appendToExpression(currentExpression, Operator.MULTIPLICATION, currentOperandValue);

    evaluateExpressions(validExpressions, equation, endIndex + 1, currentExpression,
      currentResult - lastOperand + (lastOperand * currentOperandValue),
      lastOperand * currentOperandValue);

    removeFromExpression(currentExpression, Operator.MULTIPLICATION, currentOperandValue);
}

Since multiplication has higher precedence than addition or subtraction, it recalculates the result by removing the effect of the previous operand and applying the multiplication to the last one.

5. Testing the Implementation

Let’s test our implementation to ensure the algorithm correctly handles various inputs and produces the expected results. To verify that an invalid equation returns no results, we’ll create a parameterized test and supply a set of incorrect expressions:

private static Stream<Arguments> equationsWithNoSolutions() {
    return Stream.of(Arguments.of("3456237490", 9191), Arguments.of("5", 0));
}

@ParameterizedTest
@MethodSource("equationsWithNoSolutions")
void givenEquationsWithNoSolutions_whenProcess_thenEmptyListIsReturned(String digits, int target) {
    final List<String> result = Backtracking.process(digits, target);
    assertTrue(result.isEmpty());
}

The test passes since neither of the provided values produces a valid equation that matches the target.

Next, let’s check if the algorithm returns the correct results when we provide valid equations:

Stream<Arguments> equationsWithValidSolutions() {
    return Stream.of(Arguments.of("1", 1, Collections.singletonList("1")), 
        Arguments.of("00", 0, Arrays.asList("0+0", "0-0", "0*0")),
        Arguments.of("123", 6, Arrays.asList("1+2+3", "1*2*3")), 
        Arguments.of("232", 8, Arrays.asList("2*3+2", "2+3*2")),
        Arguments.of("534", -7, Collections.singletonList("5-3*4")), 
        Arguments.of("1010", 20, Collections.singletonList("10+10")),
        Arguments.of("1234", 10, Arrays.asList("1+2+3+4", "1*2*3+4")), 
        Arguments.of("1234", -10, Collections.singletonList("1*2-3*4")),
        Arguments.of("12345", 15, Arrays.asList("1+2+3+4+5", "1*2*3+4+5", "1-2*3+4*5", "1+23-4-5")));
}

@ParameterizedTest
@MethodSource("equationsWithValidSolutions")
void givenEquationsWithValidSolutions_whenProcess_thenValidResultsAreReturned(
  String digits, int target, List<String> expectedSolutions) {
    List<String> result = Backtracking.process(digits, target);

    assertEquals(expectedSolutions.size(), result.size());

    expectedSolutions.stream()
      .map(result::contains)
      .forEach(Assertions::assertTrue);
}

First, we check that the result count matches the expected number of solutions. Then, we ensure that each of the expected solutions is in the result list. This verifies that the algorithm correctly identifies all valid expressions.

6. Complexity Analysis

The algorithm uses backtracking to try all possible operator combinations between digits. Since we can form multi-digit numbers, we also have the option to merge the current digit with the previous one. Hence, we can insert either none or one of three operators (+, -, *) for each position between digits. With n digits, there are n-1 positions. Each position has four possible choices, resulting in approximately 4^(n-1) possible combinations.

Furthermore, each recursive call processes a number, updates the expression, and checks if it matches the target, taking O(n) time per call. Therefore, the total time complexity is O(4^(n-1) * n).

On the other hand, we can break the space complexity down into two key factors. First is the recursion stack. Since each recursive call processes a single digit, the recursion depth is O(n). Second, the expressions are stored in the result list. As the algorithm generates all valid expressions, the number of expressions is O(4^(n-1)), with each expression having a length of O(n). Therefore, the space needed to store the valid expressions is O(4^(n-1) * n), making the total space complexity O(n + 4^(n-1) * n).

7. Conclusion

In this article, we’ve learned how to generate valid expressions by inserting binary operators between digits to match a target value. The backtracking algorithm efficiently explores all possible solutions, making it a powerful tool for similar combinatorial problems.