Expression Add Operators - Practice Coding Problems

Expression Add Operators - 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: Operands in the returned expressions should not contain leading zeros unless the operand is 0 itself. A number can contain multiple digits.

Input & Output

Example 1 — Basic Case

$ Input: num = "232", target = 8

› Output: ["2*3+2", "2+3*2"]

💡 Note: 2*3+2 = 8 and 2+3*2 = 8. Both expressions evaluate to target 8.

Example 2 — Single Digit

$ Input: num = "3", target = 3

› Output: ["3"]

💡 Note: Only one way: the number itself equals the target.

Example 3 — No Solution

$ Input: num = "123", target = 0

› Output: []

💡 Note: No combination of +, -, * operators can make 123 digits equal 0.

Constraints

1 ≤ num.length ≤ 10
num consists of only digits
-2³¹ ≤ target ≤ 2³¹ - 1

Visualization

Tap to expand

Understanding the Visualization

Input

String of digits and target number

Process

Try all ways to split digits and insert +, -, * operators

Output

All valid expressions that evaluate to target

Key Takeaway

🎯 Key Insight: Handle multiplication precedence by tracking the last operand separately during backtracking

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is tracking the last operand separately to handle multiplication precedence correctly. The backtracking approach recursively builds expressions while maintaining current sum and last operand state. Time: O(3^n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Combinations	O(4^n × n)	O(4^n)	Generate all possible ways to split numbers and place operators, then evaluate each
Backtracking with Precedence	O(3^n)	O(n)	Recursively build expressions while tracking multiplication precedence correctly

Generate All Combinations — Algorithm Steps

Generate all ways to split the string into numbers (avoiding leading zeros)
For each split, generate all operator combinations between numbers
Evaluate each expression and collect those that equal target

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Numbers

Generate all valid ways to split digits

Add Operators

Try +, -, * between each pair

Evaluate

Check which expressions equal target

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char** solution(char* num, int target, int* returnSize) {
    // Implementation would be complex in C
    *returnSize = 0;
    return NULL;
}

int main() {
    char num[20];
    int target;
    
    fgets(num, sizeof(num), stdin);
    num[strcspn(num, "\n")] = 0;
    scanf("%d", &target);
    
    int returnSize;
    char** result = solution(num, target, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^n × n)

4^n combinations (3 operators + 1 no-split per position), n for evaluation

✓ Linear Growth

Space Complexity

O(4^n)

Stores all possible expressions before filtering

⚡ Linearithmic Space

180.0K Views

Medium Frequency

~25 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler