Log inSign up
hardLeetCodeNot Started

Expression Add Operators

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on LeetCode
Lesson

Problem Statement

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 · Target 6 with 123:

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 · Target 8 with 232:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]
Explanation: 2*3+2 = 8 and 2+3*2 = 8.

Example 3 · Target 0 with 105:

Input: num = "105", target = 5
Output: ["1*0+5", "10-5"]
Explanation: 1*0+5 = 5 and 10-5 = 5. Note that 105 does not have leading zeroes.

Example 4 · Target 0 with 00:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]
Explanation: 0+0 = 0, 0-0 = 0, 0*0 = 0. Note 00 is not a valid single operand due to leading zero.

Constraints:

  • 1 <= num.length <= 10
  • num consists of only digits.
  • -231 <= target <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master online precedence correction (val - prev + prev * curr) in arithmetic backtracking.
  • Understand operand string partitioning with leading zero validation.
  • Prevent 32-bit overflow using 64-bit integer arithmetic.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Insert arithmetic operators (+, -, *) into digit strings
  • Evaluate to target with proper operator precedence
  • Strict prohibition against operands with leading zeros

Algorithmic Decision Tree:

  • Loop i from index to num.length - 1 to extract operand substring sub = num.substring(index, i + 1).
  • If sub.length > 1 && sub[0] == '0', break loop (leading zero pruning).
  • For +: solve(i + 1, expr + '+' + sub, val + num, +num).
  • For -: solve(i + 1, expr + '-' + sub, val - num, -num).
  • For *: solve(i + 1, expr + '*' + sub, val - prev + (prev * num), prev * num).

Connected Patterns:

Basic CalculatorRestore IP AddressesPalindrome Partitioning

1. Generate All Operator Strings + Calculator Evaluator

Intuition

Between N digits, there are N-1 slots, each taking 1 of 4 choices (empty, +, -, *), generating 4^(N-1) expression strings. Each string is verified for leading zeros and passed to a full stack-based arithmetic evaluator.

When to apply: Baseline comparison to illustrate the benefit of maintaining running evaluations.

Algorithm

  1. Generate all 4^(N-1) possible expression strings.
  2. Check each expression string to ensure no multi-digit number starts with 0.
  3. Evaluate the expression using standard BODMAS/PEMDAS evaluator.
  4. If evaluated value == target, add expression to result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <stack>
5#include <cctype>
6
7using namespace std;
8
9class Solution {
10 long long evaluate(const string& s) {
11 stack<long long> st;
12 char sign = '+';
13 long long num = 0;
14 int n = s.length();
15 for (int i = 0; i < n; i++) {
16 char c = s[i];
17 if (isdigit(c)) num = num * 10 + (c - '0');
18 if (i == n - 1 || (!isdigit(c))) {
19 if (sign == '+') st.push(num);
20 else if (sign == '-') st.push(-num);
21 else if (sign == '*') {
22 long long top = st.top(); st.pop();
23 st.push(top * num);
24 }
25 sign = c;
26 num = 0;
27 }
28 }
29 long long total = 0;
30 while (!st.empty()) { total += st.top(); st.pop(); }
31 return total;
32 }
33
34 bool isValid(const string& s) {
35 int n = s.length();
36 for (int i = 0; i < n; i++) {
37 if (s[i] == '0') {
38 if (i == 0 || !isdigit(s[i - 1])) {
39 if (i + 1 < n && isdigit(s[i + 1])) return false; // leading zero
40 }
41 }
42 }
43 return true;
44 }
45
46public:
47 void generate(int idx, const string& num, string current, vector<string>& result, long long target) {
48 if (idx == num.length()) {
49 if (isValid(current) && evaluate(current) == target) {
50 result.push_back(current);
51 }
52 return;
53 }
54
55 char nextChar = num[idx];
56 // 4 choices
57 generate(idx + 1, num, current + nextChar, result, target);
58 generate(idx + 1, num, current + "+" + nextChar, result, target);
59 generate(idx + 1, num, current + "-" + nextChar, result, target);
60 generate(idx + 1, num, current + "*" + nextChar, result, target);
61 }
62
63 vector<string> addOperators(string num, int target) {
64 vector<string> result;
65 if (num.empty()) return result;
66 string initial = "";
67 initial += num[0];
68 generate(1, num, initial, result, target);
69 return result;
70 }
71};
72
73int main() {
74 Solution sol;
75 auto res = sol.addOperators("123", 6);
76 for (const string& s : res) cout << s << " ";
77 cout << endl;
78 return 0;
79}

Time & Space Complexity

  • Time complexity: O(4^N * N) — Generates 4^(N-1) strings, and evaluates each string in O(N) time with a stack.
  • Space complexity: O(N) — String buffers and expression parser stack take O(N) memory.

2. Partition Backtracking with String Slicing

Intuition

Iterate i from index to n-1. Extract substring sub = num[index..i]. If sub has leading zero, break. For +, -, *, compute new running values immediately using prevOperand to fix multiplication precedence.

When to apply: When building string expressions cleanly without manual char buffers.

Algorithm

  1. Iterate i from idx to num.length - 1.
  2. Extract sub and convert to integer val.
  3. If sub.length > 1 && sub[0] == '0', break.
  4. If idx == 0: recurse with path = sub, val = val, prev = val.
  5. Otherwise: recurse for +, -, and * with precedence formulas.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 void backtrack(int idx, const string& num, long long target,
9 string path, long long val, long long prev,
10 vector<string>& result) {
11 if (idx == num.length()) {
12 if (val == target) result.push_back(path);
13 return;
14 }
15
16 for (int i = idx; i < num.length(); i++) {
17 if (i > idx && num[idx] == '0') break; // leading zero
18
19 string part = num.substr(idx, i - idx + 1);
20 long long curr = stoll(part);
21
22 if (idx == 0) {
23 backtrack(i + 1, num, target, part, curr, curr, result);
24 } else {
25 backtrack(i + 1, num, target, path + "+" + part, val + curr, curr, result);
26 backtrack(i + 1, num, target, path + "-" + part, val - curr, -curr, result);
27 backtrack(i + 1, num, target, path + "*" + part, val - prev + prev * curr, prev * curr, result);
28 }
29 }
30 }
31
32public:
33 vector<string> addOperators(string num, int target) {
34 vector<string> result;
35 backtrack(0, num, target, "", 0, 0, result);
36 return result;
37 }
38};
39
40int main() {
41 Solution sol;
42 auto res = sol.addOperators("232", 8);
43 for (const string& s : res) cout << s << " ";
44 cout << endl;
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(4^N * N) — String slicing and concatenation take O(N) per branch.
  • Space complexity: O(N) — Call stack depth is bounded by N.

3. Zero-Allocation Char Buffer Backtracking (Optimal)

Intuition

Pre-allocate a char buffer of size 2 * N. Write characters directly into buffer positions. When a branch finishes, create string from buffer length only for successful targets. Compute running sum and previous operand inline.

When to apply: Optimal high-performance backtracking solution maximizing throughput.

Algorithm

  1. Allocate char array buf of size 2 * N.
  2. In backtrack(numIdx, bufIdx, val, prev):
  3. - If numIdx == n: if val == target, convert buf[0..bufIdx] to string and add to result.
  4. - Loop i from numIdx to n - 1:
  5. - Accumulate curr = curr * 10 + (num[i] - '0').
  6. - Write digits into buf.
  7. - For first number: recurse with val = curr, prev = curr.
  8. - For +: set buf[op] = '+', recurse val + curr, prev = curr.
  9. - For -: set buf[op] = '-', recurse val - curr, prev = -curr.
  10. - For *: set buf[op] = '*', recurse val - prev + prev * curr, prev = prev * curr.

Multiplication Precedence State Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Step 1: First operand is '2'
Visual state
Values and pointers at this exact step
tree
Initial Operand
path: 2, val: 2, prev: 2

Node order shown; add connections to display explicit tree edges.

Variables at this step
idx
1
path
2
val
2
prev
2
Why this step matters

Step 1: First operand is 2. val = 2, prev = 2, path = '2'.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4
5using namespace std;
6
7class Solution {
8 void dfs(int numIdx, int bufIdx, long long val, long long prev,
9 const string& num, long long target, vector<char>& buf, vector<string>& result) {
10 int n = num.length();
11 if (numIdx == n) {
12 if (val == target) {
13 result.emplace_back(buf.data(), bufIdx);
14 }
15 return;
16 }
17
18 long long curr = 0;
19 int opIdx = bufIdx;
20 if (numIdx > 0) bufIdx++; // reserve slot for operator
21
22 for (int i = numIdx; i < n; i++) {
23 if (i > numIdx && num[numIdx] == '0') break; // leading zero
24
25 curr = curr * 10 + (num[i] - '0');
26 buf[bufIdx++] = num[i];
27
28 if (numIdx == 0) {
29 dfs(i + 1, bufIdx, curr, curr, num, target, buf, result);
30 } else {
31 buf[opIdx] = '+';
32 dfs(i + 1, bufIdx, val + curr, curr, num, target, buf, result);
33
34 buf[opIdx] = '-';
35 dfs(i + 1, bufIdx, val - curr, -curr, num, target, buf, result);
36
37 buf[opIdx] = '*';
38 dfs(i + 1, bufIdx, val - prev + prev * curr, prev * curr, num, target, buf, result);
39 }
40 }
41 }
42
43public:
44 vector<string> addOperators(string num, int target) {
45 vector<string> result;
46 if (num.empty()) return result;
47 vector<char> buf(2 * num.length());
48 dfs(0, 0, 0, 0, num, target, buf, result);
49 return result;
50 }
51};
52
53int main() {
54 Solution sol;
55 auto res = sol.addOperators("105", 5);
56 for (const string& s : res) cout << s << " ";
57 cout << endl;
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(4^N * N) — Generates all valid operator placements, avoiding intermediate string allocation overheads.
  • Space complexity: O(N) — Uses a single preallocated buffer of size 2*N and O(N) call stack.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Generate Strings + Calculator EvaluatorO(4^N * N)O(N)Generate all operator strings, validate leading zeros, and evaluate via stack.Full stack evaluation per expression
2.Partition Backtracking with String SlicingO(4^N * N)O(N)Maintain running value and previous operand with string concatenation.String concat allocations
3.Zero-Allocation Char Buffer BacktrackingOptimalO(4^N * N)O(N)Pre-allocated char buffer with in-place character writes.Exponential combination count

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Using standard 32-bit signed integers, which overflow on multi-digit multiplications like 109 * 109.

Pitfall 2:

Forgetting to subtract prev before adding prev * curr in multiplication.

Pitfall 3:

Using continue instead of break for leading zeros, which would continue to test even longer invalid numbers like '056'.

Crucial Edge Cases to Validate:

  • Leading Zeroes in Partitions: 105 -> 10-5 and 1*0+5 (rejects 1*05).
  • Single Zero: 00, target 0 -> [0+0, 0-0, 0*0].
  • Negative Target: target < 0 -> handles negative sums properly with -num.
  • Overflow in Multiplications: 32-bit overflow prevented by using 64-bit long long.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Walk the interviewer through the 2 + 3 * 2 multiplication precedence formula step by step.
  2. Always specify 64-bit long integer arithmetic to highlight precision awareness.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why do we calculate val - prev + (prev * curr) when encountering a multiplication operator?

2.How do we prune numbers with leading zeros like '05'?

Back to DSA Sheet