Expression Add Operators solution and explanation
Google
9 more videos on this problem
Expression Add Operators | Leetcode 282 | Live coding session 🔥🔥🔥Coding Decoded · 12:07 · 19K views
EXPRESSION ADD OPERATORS | LEETCODE # 282 | PYTHON SOLUTIONCracking FAANG · 24:05 · 16K views
Expression Add operators | Leetcode | Hard | Java | Striver's A to Z DSA Course/SheetAlgorithmHQ · 23:01 · 14K views
Leetcode 282: Expression Add Operators | Master Backtracking | Intuition and ApproachCode Concepts with Animesh · 32:20 · 10K views
LeetCode 282. Expression Add OperatorsHappy Coding · 18:37 · 7K views
Leetcode 282 Expression Add OperatorsRen Zhang · 22:09 · 3K views
LeetCode 282. Expression Add Operators Explanation and Solutionhappygirlzt · 15:36 · 3K views
Leetcode - Expression Add Operators (Python)Timothy H Chang · 10:33 · 2K views
Expression Add Operators | 282. Expression Add Operators | GFG POTD | LEETCODE | CPP | C++Deepak Joshi · 23:25 · 1K views
Daily Leetcode #536: Sep 18, 2021 - 282. Expression Add OperatorsProgramming Live with Larry · 36:10 · 478 views
The problem
Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.
Note that operands in the returned expressions should not contain leading zeros.
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 overview
Problem Overview: Given a numeric string and a target value, insert the operators +, -, and * between digits so the resulting expression evaluates exactly to the target. You must return all valid expressions while respecting operator precedence, especially multiplication.
Approach 1: Generate All Expressions + Evaluate (Brute Force) (Time: O(4^n * n), Space: O(n))
The most direct idea is to generate every possible expression by inserting an operator or choosing to extend the current number at each position. After constructing an expression string, evaluate it using a stack-based expression evaluator or a parser. This guarantees correctness but wastes time building many expressions that never match the target. Each expression evaluation takes O(n) time, and there are roughly 4^n operator placements (three operators or concatenation). This approach is useful conceptually because it clarifies the search space, but it performs redundant evaluation work.
Approach 2: Recursive Backtracking with Running Evaluation (Time: O(4^n), Space: O(n))
The efficient strategy builds expressions while simultaneously tracking their evaluated value. During recursion, maintain three pieces of state: the current index in the string, the current calculated value, and the last operand used. The last operand is necessary to correctly handle multiplication precedence. When adding *, subtract the previous operand from the running total and add the multiplied value instead (value - prev + prev * current). This simulates operator precedence without re-evaluating the entire expression.
At each recursion step, iterate over possible numeric substrings starting from the current index. Skip numbers with leading zeros (for example "05"). For the first number, start the expression without adding an operator. For subsequent numbers, recursively try +, -, and *. This pruning strategy ensures every partial expression maintains a correct running value, avoiding full expression parsing.
This technique combines backtracking with incremental evaluation over a string input while applying arithmetic rules from math. The recursion depth is at most n, and each step branches into multiple operator choices, giving exponential complexity but with minimal overhead.
Recommended for interviews: Recursive backtracking with running evaluation is the expected solution. Interviewers want to see how you manage operator precedence without re-parsing the expression each time. Starting with the brute force idea shows you understand the search space, but optimizing with a running total and previous operand demonstrates strong recursion and backtracking skills.
Solution
This approach involves using a recursive backtracking algorithm to explore all possible combinations of the operators between the digits. The algorithm tries to build expressions from the input string by considering each possible position for inserting an operator. It is essential to keep track of the current value of the expression, the previous operand (to handle multiplication correctly with due precedence), and the current path (the expression string being built).
We also need to ensure that no operand in the expression starts with a zero unless the operand is zero itself to avoid leading zero issues.
class Solution:
def addOperators(self, num: str, target: int):
def helper(num, target, pos, eval, multed, path, result):
if pos == len(num):
if eval == target:
result.append(path)
return
for i in range(pos, len(num)):
if i != pos and num[pos] == '0':
break
currStr = num[pos:i+1]
curr = int(currStr)
if pos == 0:
helper(num, target, i + 1, curr, curr, currStr, result)
else:
helper(num, target, i + 1, eval + curr, curr, path + '+' + currStr, result)
helper(num, target, i + 1, eval - curr, -curr, path + '-' + currStr, result)
helper(num, target, i + 1, eval - multed + multed * curr, multed * curr, path + '*' + currStr, result)
result = []
helper(num, target, 0, 0, 0, '', result)
return result
# Example usage:
solution = Solution()
print(solution.addOperators("123", 6))import java.util.*;
public class Solution {
public List<String> addOperators(String num, int target) {
List<String> result = new ArrayList<>();
helper(num, target, 0, 0, 0, "", result);
return result;
}
private void helper(String num, int target, int pos, long eval, long multed, String path, List<String> result) {
if (pos == num.length()) {
if (eval == target) {
result.add(path);
}
return;
}
for (int i = pos; i < num.length(); i++) {
if (i != pos && num.charAt(pos) == '0') break;
String currStr = num.substring(pos, i + 1);
long curr = Long.parseLong(currStr);
if (pos == 0) {
helper(num, target, i + 1, curr, curr, currStr, result);
} else {
helper(num, target, i + 1, eval + curr, curr, path + "+" + currStr, result);
helper(num, target, i + 1, eval - curr, -curr, path + "-" + currStr, result);
helper(num, target, i + 1, eval - multed + multed * curr, multed * curr, path + "*" + currStr, result);
}
}
}
public static void main(String[] args) {
Solution solution = new Solution();
List<String> results = solution.addOperators("123", 6);
System.out.println(results);
}
}#include <vector>
#include <string>
using namespace std;
class Solution {
public:
void helper(string num, int target, int pos, long eval, long multed, string path, vector<string>& result) {
if (pos == num.size()) {
if (eval == target) {
result.push_back(path);
}
return;
}
for (int i = pos; i < num.size(); i++) {
if (i != pos && num[pos] == '0') break;
string currStr = num.substr(pos, i - pos + 1);
long curr = stol(currStr);
if (pos == 0) {
helper(num, target, i + 1, curr, curr, currStr, result);
} else {
helper(num, target, i + 1, eval + curr, curr, path + "+" + currStr, result);
helper(num, target, i + 1, eval - curr, -curr, path + "-" + currStr, result);
helper(num, target, i + 1, eval - multed + multed * curr, multed * curr, path + "*" + currStr, result);
}
}
}
vector<string> addOperators(string num, int target) {
vector<string> result;
helper(num, target, 0, 0, 0, "", result);
return result;
}
};
int main() {
Solution solution;
vector<string> results = solution.addOperators("123", 6);
for (auto& expr : results) {
printf("%s\n", expr.c_str());
}
return 0;
}var addOperators = function(num, target) {
const result = [];
function helper(pos, eval, multed, path) {
if (pos === num.length) {
if (eval === target) {
result.push(path);
}
return;
}
for (let i = pos; i < num.length; i++) {
if (i !== pos && num[pos] === '0') break;
const currStr = num.substring(pos, i + 1);
const curr = Number(currStr);
if (pos === 0) {
helper(i + 1, curr, curr, currStr);
} else {
helper(i + 1, eval + curr, curr, path + '+' + currStr);
helper(i + 1, eval - curr, -curr, path + '-' + currStr);
helper(i + 1, eval - multed + multed * curr, multed * curr, path + '*' + currStr);
}
}
}
helper(0, 0, 0, "");
return result;
};
// Example usage:
console.log(addOperators("123", 6));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void helper(char *num, int target, int pos, long eval, long multed, char *path, char **result, int *returnSize) {
if (pos == strlen(num)) {
if (eval == target) {
result[*returnSize] = strdup(path);
(*returnSize)++;
}
return;
}
for (int i = pos; i < strlen(num); i++) {
if (i != pos && num[pos] == '0') break;
char *curr_num_str = strndup(num + pos, i - pos + 1);
long current_num = atol(curr_num_str);
int len = strlen(path);
if (pos == 0) {
sprintf(path + len, "%s", curr_num_str);
helper(num, target, i + 1, current_num, current_num, path, result, returnSize);
path[len] = '\0';
} else {
sprintf(path + len, "+%s", curr_num_str);
helper(num, target, i + 1, eval + current_num, current_num, path, result, returnSize);
path[len] = '\0';
sprintf(path + len, "-%s", curr_num_str);
helper(num, target, i + 1, eval - current_num, -current_num, path, result, returnSize);
path[len] = '\0';
sprintf(path + len, "*%s", curr_num_str);
helper(num, target, i + 1, eval - multed + multed * current_num, multed * current_num, path, result, returnSize);
path[len] = '\0';
}
free(curr_num_str);
}
}
char **addOperators(char *num, int target, int *returnSize) {
*returnSize = 0;
char **result = (char **)malloc(1000 * sizeof(char *));
char *path = (char *)malloc((2 * strlen(num) + 1) * sizeof(char));
helper(num, target, 0, 0, 0, path, result, returnSize);
free(path);
return result;
}
int main() {
char *num = "123";
int target = 6;
int returnSize;
char **result = addOperators(num, target, &returnSize);
printf("[ ");
for (int i = 0; i < returnSize; i++) {
printf("\"%s\", ", result[i]);
free(result[i]);
}
printf("]\n");
free(result);
return 0;
}using System;
using System.Collections.Generic;
public class Solution {
public IList<string> AddOperators(string num, int target) {
List<string> result = new List<string>();
Helper(num, target, 0, 0, 0, "", result);
return result;
}
private void Helper(string num, int target, int pos, long eval, long multed, string path, List<string> result) {
if (pos == num.Length) {
if (eval == target) {
result.Add(path);
}
return;
}
for (int i = pos; i < num.Length; i++) {
if (i != pos && num[pos] == '0') break;
string currStr = num.Substring(pos, i - pos + 1);
long curr = long.Parse(currStr);
if (pos == 0) {
Helper(num, target, i + 1, curr, curr, currStr, result);
} else {
Helper(num, target, i + 1, eval + curr, curr, path + "+" + currStr, result);
Helper(num, target, i + 1, eval - curr, -curr, path + "-" + currStr, result);
Helper(num, target, i + 1, eval - multed + multed * curr, multed * curr, path + "*" + currStr, result);
}
}
}
public static void Main() {
Solution solution = new Solution();
IList<string> results = solution.AddOperators("123", 6);
foreach (string expr in results) {
Console.WriteLine(expr);
}
}
}The Python solution uses a nested `helper` function to apply a recursive backtracking algorithm to explore the expression possibilities, updating the current valid path with the appropriate operators inserted between segments of the input string "num".
Time Complexity: O(4^n), considering each combination of operators we apply between segments.
Space Complexity: O(n), for the call stack used during recursion and result storage.
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Generate All Expressions + Evaluate | O(4^n * n) | O(n) | Good for understanding the full search space and verifying correctness conceptually |
| Recursive Backtracking with Running Evaluation | O(4^n) | O(n) | Best general solution for interviews; avoids repeated expression evaluation |
Frequently asked questions
Is Expression Add Operators easy or hard?
Expression Add Operators is classified as a hard problem. The difficulty comes from combining backtracking with correct arithmetic evaluation, especially handling multiplication precedence without re-parsing the entire expression.
Expression Add Operators Python/Java solution
Python and Java implementations typically use DFS recursion. The function tracks the current index, accumulated value, and previous operand while building the expression string. When the index reaches the end and the value equals the target, the expression is added to the result list.
How to solve Expression Add Operators in O(n)?
An O(n) solution is not possible because the problem requires exploring many possible operator placements. The number of valid expressions grows exponentially with the number of digits. The optimal practical approach is recursive backtracking with incremental evaluation, which runs in roughly O(4^n).
What is the best approach for Expression Add Operators?
Recursive backtracking with a running evaluation is the best approach. It builds expressions digit by digit while tracking the current value and the previous operand to correctly handle multiplication precedence. This avoids re-evaluating full expressions each time and keeps the complexity around O(4^n).
Is Expression Add Operators asked at Google/Amazon/Meta?
Expression Add Operators has appeared in interviews at companies such as Google, Amazon, and Meta. It tests recursion, backtracking, and handling operator precedence during expression evaluation. Candidates are expected to manage state carefully during DFS exploration.
What data structure is used in Expression Add Operators?
The main technique uses recursion with backtracking over a string. Instead of a separate data structure like a stack or hash map, the algorithm maintains a running total and the previous operand to simulate operator precedence while constructing expressions.
What is the time complexity of Expression Add Operators?
The typical solution runs in O(4^n) time where n is the length of the input string. Each position can branch into multiple choices: extend the number or insert one of three operators. Space complexity is O(n) due to recursion depth and expression construction.