282. Expression Add Operators


Problem Description

The task is to take a string num that is composed exclusively of digits and an integer target, then find all the different ways to insert the binary operators '+', '-', and '*' between the digits in num so that the resulting expression equals the target. For example, if num = "123" and target = 6, one way to reach the target is to insert the '+' operator as "1+2+3".

A few important points to note for this problem:

  • You can insert an operator between any two digits in the string num.
  • The expressions that you create should not have numbers with leading zeroes.
  • The order of digits in the num string must remain the same.

The challenge is to generate all such valid expressions that evaluate to target.

Flowchart Walkthrough

Let's use the algorithm flowchart found here to determine the appropriate strategy for solving LeetCode problem 282, Expression Add Operators. Here's the step-by-step analysis using the predefined nodes and edges of our flowchart:

  1. Is it a graph?

    • No: The problem does not address relationships or connections like graph problems do. It deals with inserting operations between numbers to achieve a target expression.
  2. Need to solve for kth smallest/largest?

    • No: The challenge is not centered around finding a kth smallest or largest element, but rather forming expressions to reach a target number.
  3. Involves Linked Lists?

    • No: The problem does not involve the manipulation or traversal of linked lists.
  4. Does the problem have small constraints?

    • Yes: The problem could be considered to have small constraints since the number of possible expressions, although potentially large, is finite and manageable with appropriate pruning in backtracking.
  5. Brute force / Backtracking?

    • Yes: Due to the need to explore multiple combinations and permutations of adding operators ‘+’, ‘-’, or ‘*’ between digits to meet the target expression, a brute force or backtracking approach seems suitable. The problem necessitates evaluating a range of possible strings generated by inserting different operators, which aligns well with the backtracking method where you try different possibilities and backtrack if they don't meet the criteria.

Conclusion: According to the flowchart, using a backtracking approach is appropriate for LeetCode 282, as it involves generating various combinations of operations and requires evaluating each to see if they satisfy the given target.

Intuition

To solve the puzzle efficiently, we use a Depth First Search (DFS) approach.

  1. Breaking Down the Problem: Since you have to evaluate all possible combinations of digits and operators, this naturally forms a tree structure with each node representing a decision to include a '+', '-', '*', or no operator before the current digit.

  2. Handling '0's: No number in the expression can have leading zeroes. This is managed by ensuring that whenever a '0' appears as a current digit, it doesn't process further if it is the start of a new operand, thus avoiding expressions with numbers like "01" or "002".

  3. Evaluating Expressions: Keep track of the current expression's value and update it as you insert new operators. This involves tracking the last operand to correctly evaluate multiplication which has higher precedence than addition and subtraction.

  4. Depth First Search (DFS) Algorithm: The key to the solution is a recursive DFS function that tries all possible combinations of operators and operand lengths. At each recursive call, the current value of the expression, path (the actual expression built so far), value of the previous operand (to handle multiplication correctly), and position in the string are updated.

  5. Base Case: Once the end of the string is reached, check whether the current value of the expression is equal to the target. If it is, add the path to the list of possible solutions.

  6. DFS Recursion: The DFS function:

    • Includes the current digit as is and moves to the next step without adding any operators if it's the first digit (to avoid leading '+', '-', or '*' characters).
    • Tries adding each of the operators (+, -, *) between the current and the next digit if it's not the first digit, carefully updating the expression's value and path. It is also critical to adjust the value of the previous operand when a multiplication is encountered due to precedence.

By implementing this DFS approach, we exhaustively search through all the possible expressions and return those that meet the target value.

Learn more about Math and Backtracking patterns.

Solution Approach

The implementation of the solution uses a recursive function to perform a depth-first search through the possible combinations of binary operators and operands. The DFS searches through the num string, trying to add an operator or not at each step, to explore all potential valid expressions that can be formed. Here is the breakdown of the key parts of the implementation:

  • Recursive Depth-First Search (DFS): A recursive function dfs is defined which facilitates the depth-first search. This recursive function takes four parameters:

    • u: The current index in the string num.
    • prev: The value of the last operand included in the expression (necessary for handling precedence in multiplication).
    • curr: The current value of the expression as it's been evaluated so far.
    • path: The current form of the expression as a string, which shows exactly how the numbers and operators are combined.
  • Base Case: The base case for recursion occurs when the end of the string num is reached (i.e., u == len(num)). Here, if the current value equals the target, the current path (the expression) is added to the answer list ans.

  • Loop Through Possible Operands: The function loops from the current index u to the end of the num string, incrementing i at each iteration. This loop determines the next operand by considering one digit at a time and then multiple digits as a single operand until a leading zero would be created, which is avoided.

  • Skip Leading Zeros: If the current digit is '0' and it's the start of a new operand, it will break the loop to avoid operands with leading zeroes.

  • Operand Conversion: The substring from the current index u up to and including i is converted to an integer named next. This integer will become the next operand for the operators to act upon.

  • No Operator for First Digit: If we are at the start of the string (when u is 0), no operator is added. The DFS function is called with the next index and values are set to include the first operand.

  • Adding Operators: If not at the start, three recursive calls are made, one for each operator ('+', '-', '*'):

    • Addition (+): The DFS is called with the cumulative value updated by adding next.
    • Subtraction (-): The DFS is called with the cumulative value updated by subtracting next.
    • Multiplication (*): The DFS is called with a more complex value update, where the last operand is first removed from the cumulative value (curr - prev) and then the multiplication of prev and next is added back to it to maintain the correct order of operations.

The dfs function is initially called with starting values, including an empty path string. Finally, the list ans is returned, containing all the paths (expressions) that evaluate to the target.

By methodically and recursively exploring each combination and path, we can generate a comprehensive list of all expressions that meet the criteria. The provided solution is both elegant and efficient in its approach to solving this problem.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach. Consider num = "105" and target = 5. We want to find all valid expressions that can be created from "105" which evaluate to 5.

Now, we'll go through each step as per the DFS algorithm strategy:

  1. Initialization: Start with an empty path, the curr value as 0, prev as 0, and an index u at 0.

  2. First Call to DFS: Since u is at the start, no operator is added. The first digit, '1', is converted to an integer and added to prev and curr. The new path becomes "1", and recursion continues to the next digit with u incremented.

  3. Second Digit - '0': At u = 1, we have to consider that '0' might be a leading zero for an operand. Since it's not the first digit, we explore adding '+', '-', and '*':

    • No Operator: Skipping any operator, prev and curr remain the same, path becomes "10", and u goes to the next digit.
    • Add '+': The function is called with curr as 10, prev as 10, and path as "10+".
    • Add '-': The function is called with curr as 10, prev as -10, and path as "10-".
    • Add '*': We don't consider multiplication here because it would lead to a result that is certainly not going to match our target of 5 (since we'd be multiplying by 0).
  4. Third Digit - '5': Now, u = 2 and the possible operands are '05' which we ignore to avoid leading zero, or just '5'.

    We again try all three possibilities from the conditions met, now with the path that already includes '10':

    • Path "10+5": For the '+' operator from the previous state "10+", adding 5 results in 15, which does not match the target. This path is abandoned.
    • Path "10-5": For the '-' operator from the previous state "10-", subtracting 5 results in 5, which matches our target. We add "10-5" to our list of answers.
    • Multiplied by '5': Multiplication would only happen if the previous operator was a '*', which wasn't a valid option in step 3, so we don't consider it here.

Since we managed to find one valid solution, "10-5" evaluates to the target of 5, which means our answer list would be ["10-5"].

By iterating through each digit in num and exploring all possible operator insertions in this manner, we systematically discover all expressions that evaluate to the given target. The DFS algorithm ensures we explore every possibility, and our logic for handling leading zeroes and operator precedence ensures all expressions are valid and correctly evaluated.

Solution Implementation

1from typing import List
2
3class Solution:
4    def addOperators(self, num: str, target: int) -> List[str]:
5        res = []
6
7        # Perform depth-first search starting from character at index `idx` in `num`
8        # `prev_operand` is the value of the operand formed just prior to the current call
9        # `current_val` is the current calculated value considering all the operators added till now
10        # `expression` is the string representation of the expression built till now
11        def dfs(idx, prev_operand, current_val, expression):
12            # When we have reached the end of the string `num`
13            if idx == len(num):
14                # If the expression's calculated value equals the target then store the expression
15                if current_val == target:
16                    res.append(expression)
17                return
18          
19            # Try out all possible splits for the current prefix
20            for i in range(idx, len(num)):
21                # Skip any number that starts with zero and has more than one digit
22                if i != idx and num[idx] == '0':
23                    break
24              
25                # The current operand, formed by the digits from idx to i inclusive
26                current_operand = int(num[idx : i + 1])
27              
28                if idx == 0:
29                    # If the index is at the beginning of 'num', we just take the current number as operand
30                    dfs(i + 1, current_operand, current_operand, str(current_operand))
31                else:
32                    # Try adding '+'
33                    dfs(i + 1, current_operand, current_val + current_operand, expression + "+" + str(current_operand))
34                    # Try adding '-'
35                    dfs(i + 1, -current_operand, current_val - current_operand, expression + "-" + str(current_operand))
36                    # Try adding '*'
37                    dfs(
38                        i + 1,
39                        prev_operand * current_operand, # this will be used in the next call to undo if we backtrack
40                        current_val - prev_operand + (prev_operand * current_operand), # undo the previous operand and apply multiplication
41                        expression + "*" + str(current_operand)
42                    )
43
44        # Start the DFS from index 0, with previous operand as 0 and current value as 0 and no expression built yet
45        dfs(0, 0, 0, "")
46        return res
47
1import java.util.ArrayList;
2import java.util.List;
3
4public class Solution {
5    private List<String> answers;  // Holds the valid expressions
6    private String number;         // The input number as a String
7    private int targetValue;       // The target value for the expressions
8
9    // Main function to find expressions that evaluate to the target value
10    public List<String> addOperators(String num, int target) {
11        answers = new ArrayList<>();
12        number = num;
13        targetValue = target;
14        recursiveSearch(0, 0, 0, "");
15        return answers;
16    }
17
18    // Helper function to perform depth-first search
19    private void recursiveSearch(int index, long prevOperand, long currentTotal, String expression) {
20        // If we've reached the end of the string, check if the currentTotal equals the target value
21        if (index == number.length()) {
22            if (currentTotal == targetValue) {
23                answers.add(expression);
24            }
25            return;
26        }
27
28        // Try all possible splits of the remainder of the string
29        for (int i = index; i < number.length(); i++) {
30            // Skip numbers with leading zeros (unless the number itself is zero)
31            if (i != index && number.charAt(index) == '0') {
32                break;
33            }
34
35            // Parse the current number substring
36            long nextOperand = Long.parseLong(number.substring(index, i + 1));
37
38            // If this is the first operand (no operator before it)
39            if (index == 0) {
40                recursiveSearch(i + 1, nextOperand, nextOperand, expression + nextOperand);
41            } else {
42                // Try adding the '+' operator
43                recursiveSearch(i + 1, nextOperand, currentTotal + nextOperand, expression + "+" + nextOperand);
44                // Try adding the '-' operator
45                recursiveSearch(i + 1, -nextOperand, currentTotal - nextOperand, expression + "-" + nextOperand);
46                // Try adding the '*' operator
47                recursiveSearch(i + 1, prevOperand * nextOperand, currentTotal - prevOperand + prevOperand * nextOperand, expression + "*" + nextOperand);
48            }
49        }
50    }
51}
52
1#include <vector>
2#include <string>
3
4class Solution {
5private:
6    std::vector<std::string> answers; // Holds the valid expressions
7    std::string number;               // The input number as a string
8    int targetValue;                  // The target value for the expressions
9
10    // Helper function to perform depth-first search
11    void recursiveSearch(size_t index, long long prevOperand, long long currentTotal, std::string expression) {
12        // If we've reached the end of the number string, check if the currentTotal equals the target value
13        if (index == number.size()) {
14            if (currentTotal == targetValue) {
15                answers.push_back(expression);
16            }
17            return;
18        }
19
20        // Try all possible splits of the remainder of the string
21        for (size_t i = index; i < number.size(); ++i) {
22            // Skip numbers with leading zeros (unless the number itself is zero)
23            if (i != index && number[index] == '0') {
24                break;
25            }
26
27            // Parse the current number substring
28            long long nextOperand = std::stoll(number.substr(index, i - index + 1));
29
30            // If this is the first operand (no operator before it)
31            if (index == 0) {
32                recursiveSearch(i + 1, nextOperand, nextOperand, expression + std::to_string(nextOperand));
33            } else {
34                // Try adding the '+' operator
35                recursiveSearch(i + 1, nextOperand, currentTotal + nextOperand, expression + "+" + std::to_string(nextOperand));
36                // Try adding the '-' operator
37                recursiveSearch(i + 1, -nextOperand, currentTotal - nextOperand, expression + "-" + std::to_string(nextOperand));
38                // Try adding the '*' operator, update the prevOperand to handle precedence of multiplication
39                recursiveSearch(i + 1, prevOperand * nextOperand, currentTotal - prevOperand + prevOperand * nextOperand, expression + "*" + std::to_string(nextOperand));
40            }
41        }
42    }
43
44public:
45    // Main function to find expressions that evaluate to the target value
46    std::vector<std::string> addOperators(std::string num, int target) {
47        // Initialize member variables
48        answers.clear();
49        number = num;
50        targetValue = target;
51        // Start the recursive search with initial values
52        recursiveSearch(0, 0, 0, "");
53        return answers;
54    }
55};
56
1// Import statements are not needed in TypeScript for defining global variables and methods.
2
3// Array to hold the valid expressions
4const answers: string[] = [];
5
6// Input number as a string
7let number: string = "";
8
9// Target value for the expressions
10let targetValue: number = 0;
11
12// Main function to find expressions that evaluate to the target value
13function addOperators(num: string, target: number): string[] {
14  // Initialize the global variables
15  answers.length = 0;   // Clear the answers array
16  number = num;
17  targetValue = target;
18
19  // Begin recursive search from index 0
20  recursiveSearch(0, 0, 0, "");
21  return answers;
22}
23
24// Helper function to perform depth-first search
25function recursiveSearch(
26  index: number,
27  prevOperand: number,
28  currentTotal: number,
29  expression: string
30): void {
31  // If we've reached the end of the string, check if the currentTotal equals the target value
32  if (index === number.length) {
33    if (currentTotal === targetValue) {
34      answers.push(expression);
35    }
36    return;
37  }
38
39  // Try all possible splits of the remainder of the string
40  for (let i = index; i < number.length; i++) {
41    // Skip numbers with leading zeros (unless the number itself is zero)
42    if (i !== index && number.charAt(index) === '0') {
43      break;
44    }
45
46    // Parse the current number substring
47    const nextOperand: number = +number.substring(index, i + 1);
48
49    // If this is the first operand (no operator before it)
50    if (index === 0) {
51      recursiveSearch(i + 1, nextOperand, nextOperand, expression + nextOperand.toString());
52    } else {
53      // Try adding the '+' operator and recurse
54      recursiveSearch(i + 1, nextOperand, currentTotal + nextOperand, `${expression}+${nextOperand}`);
55      // Try adding the '-' operator and recurse
56      recursiveSearch(i + 1, -nextOperand, currentTotal - nextOperand, `${expression}-${nextOperand}`);
57      // Try adding the '*' operator and recurse
58      recursiveSearch(
59        i + 1,
60        prevOperand * nextOperand,
61        currentTotal - prevOperand + prevOperand * nextOperand,
62        `${expression}*${nextOperand}`
63      );
64    }
65  }
66}
67
68// Note: Since we're defining these as global, we're omitting the `export` statement that would otherwise be used in a module context to export the function or constants.
69

Time and Space Complexity

The provided Python function addOperators seeks to insert arithmetic operators into a string representing a number in all possible ways such that the resulting expression evaluates to a given target value. To analyze its time and space complexity, we have to understand how the recursion is structured.

The recursion explores adding '+', '-', or '*' between every two digits in the string. For a string of length n, there are n-1 interstitial positions where operators can be placed. Since there are 3 different operators to choose from at each interstitial position, in the worst case, the number of different expressions generated is up to O(3^(n-1)). Thus, the time complexity of this recursive solution can be expressed as O(3^n) to account for this explosive growth due to branching at each character position. This is assuming the time taken to compute the next component of the expression and concatenate strings is negligible in comparison to the recursion itself.

Now, considering the space complexity, there are two aspects to consider:

  1. The recursion stack depth, which in the worst case can go up to n - the depth equals the length of the string if the recursion explores adding an operator after every digit. This contributes O(n) to the space complexity.

  2. The space for storing the paths (partial expressions). Since the function concatenates strings to build up expressions, the maximum length of a path could be 2n-1 (for n digits, and n-1 operators). Since it only keeps a single path in memory at any one time during the recursion, the space taken by the path does not have a multiplicative effect based on the number of function calls.

Taking into account both the recursion stack and the path length, the space complexity of the algorithm can be concluded to be O(n).

In summary:

  • Time Complexity: O(3^n)
  • Space Complexity: O(n)

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

How many ways can you arrange the three letters A, B and C?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!


Load More