Expression Add Operators - In-Depth Explanation

The Expression Add Operators problem is a classic LeetCode challenge where you’re given a string containing digits and a target value. The goal is to add binary operators (+, -, or *) between the digits so that the expression evaluates to the target value. This problem involves exploring all possible combinations of adding operators and evaluating them to find valid expressions. In this blog post, we will solve this problem using Backtracking and then optimize it using Memoization.

Problem Description

Given a string num that contains only digits and an integer target, return all possible combinations of the string that evaluate to the target value when binary operators are added between the digits.

Example

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"]

Constraints

• 1 <= num.length <= 10
• num consists of digits only.
• -2^31 <= target <= 2^31 - 1

Table of Contents

1. Backtracking Solution
2. Memoization Solution
3. Visualizing Recursion with Mermaid
4. Conclusion

Backtracking Solution

The backtracking approach involves exploring all possible ways of inserting operators between the digits. At each step, we decide whether to add a +, -, or * operator or to concatenate the next digit to the current operand. We recursively evaluate all possible expressions and add those that meet the target value to our result.

Code Implementation

function addOperators(num: string, target: number): string[] {
  const results: string[] = [];

  function backtrack(index: number, path: string, calc: number, tail: number) {
    if (index === num.length) {
      if (calc === target) {
        results.push(path);
      }
      return;
    }

    for (let i = index; i < num.length; i++) {
      // Skip numbers with leading zeroes
      if (i !== index && num[index] === '0') break;

      const currentStr = num.substring(index, i + 1);
      const currentNum = parseInt(currentStr, 10);

      if (index === 0) {
        // First number, start of expression
        backtrack(i + 1, currentStr, currentNum, currentNum);
      } else {
        // Addition
        backtrack(i + 1, path + '+' + currentStr, calc + currentNum, currentNum);
        // Subtraction
        backtrack(i + 1, path + '-' + currentStr, calc - currentNum, -currentNum);
        // Multiplication
        backtrack(
          i + 1,
          path + '*' + currentStr,
          calc - tail + tail * currentNum,
          tail * currentNum
        );
      }
    }
  }

  backtrack(0, '', 0, 0);
  return results;
}

Explanation

1. Base Case: When index equals the length of num, we check if the current calculated value (calc) equals the target. If it does, we add the path to the results.

2. Recursive Step: For each possible split of the input string from index to i, we consider adding each operator (+, -, *) between the digits and recursively calculate the new values.

3. Handling Leading Zeros: If the current number has leading zeros, we skip to avoid invalid expressions.

Memoization Solution

Memoization can be applied to optimize the above backtracking solution by caching the results of overlapping subproblems. This prevents re-computation and speeds up the solution.

Code Implementation

function addOperatorsMemo(num: string, target: number): string[] {
  const results: string[] = [];
  const memo = new Map<string, string[]>();

  function backtrack(index: number, path: string, calc: number, tail: number): string[] {
    const key = `${index}-${calc}-${tail}`;
    if (memo.has(key)) return memo.get(key);

    if (index === num.length) {
      if (calc === target) {
        return [path];
      }
      return [];
    }

    const res: string[] = [];

    for (let i = index; i < num.length; i++) {
      if (i !== index && num[index] === '0') break;

      const currentStr = num.substring(index, i + 1);
      const currentNum = parseInt(currentStr, 10);

      if (index === 0) {
        res.push(...backtrack(i + 1, currentStr, currentNum, currentNum));
      } else {
        res.push(...backtrack(i + 1, path + '+' + currentStr, calc + currentNum, currentNum));
        res.push(...backtrack(i + 1, path + '-' + currentStr, calc - currentNum, -currentNum));
        res.push(
          ...backtrack(
            i + 1,
            path + '*' + currentStr,
            calc - tail + tail * currentNum,
            tail * currentNum
          )
        );
      }
    }

    memo.set(key, res);
    return res;
  }

  results.push(...backtrack(0, '', 0, 0));
  return results;
}

Explanation

The memoized version stores results of subproblems indexed by the combination of index, calc, and tail values. This prevents redundant computation of the same states.

Visualizing Recursion

Below is a Mermaid diagram to visualize the recursion state for a smaller example input using backtracking. Let’s consider num = "123" and target = 6:

mermaid

Explanation of the Diagram

• Each node represents a recursive call with the current path.
• The arrows show the different operations applied to form new expressions.
• This visual representation helps understand the branching nature of the recursion for adding operators.

Conclusion

The “Expression Add Operators” problem is an excellent example of a problem that can be tackled using backtracking and optimized with memoization. The backtracking approach explores all possible combinations by recursively adding operators, while memoization speeds up the solution by caching previously computed states. Visualizing recursion provides a deeper understanding of how the recursive calls unfold.