Different Ways to Add Parentheses - Practice Coding Problems

Different Ways to Add Parentheses - Problem

Given a string expression of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. You may return the answer in any order.

The test cases are generated such that the output values fit in a 32-bit integer and the number of different results does not exceed 10⁴.

Input & Output

Example 1 — Basic Case

$ Input: expression = "2-1-1"

› Output: [0,2]

💡 Note: Two ways to parenthesize: ((2-1)-1) = 0 and (2-(1-1)) = 2

Example 2 — Multiple Operators

$ Input: expression = "2*3-4*5"

› Output: [-34,-14,-10,-10,10]

💡 Note: Five ways to parenthesize giving different results based on operator precedence changes

Example 3 — Single Number

$ Input: expression = "2"

› Output: [2]

💡 Note: Only one way to evaluate a single number

Constraints

1 ≤ expression.length ≤ 20
expression consists of digits and the operators '+', '-', and '*'
All the integer values in the input expression are in the range [0, 99]

Visualization

Tap to expand

Understanding the Visualization

Input

Expression "2-1-1" with operators

Process

Try all possible parentheses placements

Output

All possible evaluation results

Key Takeaway

🎯 Key Insight: Each operator can be the last operation - use divide-and-conquer to explore all possibilities

Asked in

G Google 42 a Amazon 35 f Facebook 28 M Microsoft 22

The key insight is to use divide-and-conquer by treating each operator as the last operation performed. Best approach is recursion with memoization to avoid redundant calculations. Time: O(4ⁿ/n^1.5), Space: O(4ⁿ/n^1.5)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(4ⁿ/n^1.5)	O(4ⁿ/n^1.5)	Try every possible way to split the expression at each operator recursively
Recursion with Memoization	O(4ⁿ/n^1.5)	O(4ⁿ/n^1.5)	Same recursive approach but cache results to avoid recalculating same subexpressions

Brute Force Recursion — Algorithm Steps

Step 1: For each operator, split expression into left and right parts
Step 2: Recursively get all results for left and right parts
Step 3: Combine all left results with all right results using current operator

Visualization

Tap to expand

Step-by-Step Walkthrough

Split Expression

Try each operator as the last operation

Recursive Solve

Get all results for left and right parts

Combine Results

Apply operator to all combinations

Code -

solution.c — C

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

int* compute(char* expr, int* returnSize) {
    int* result = malloc(10000 * sizeof(int));
    *returnSize = 0;
    
    int len = strlen(expr);
    
    // Try splitting at each operator
    for (int i = 0; i < len; i++) {
        char c = expr[i];
        if (c == '+' || c == '-' || c == '*') {
            // Create left and right substrings
            char* left = malloc((i + 1) * sizeof(char));
            char* right = malloc((len - i) * sizeof(char));
            strncpy(left, expr, i);
            left[i] = '\0';
            strcpy(right, expr + i + 1);
            
            int leftSize, rightSize;
            int* leftResults = compute(left, &leftSize);
            int* rightResults = compute(right, &rightSize);
            
            // Combine all left and right results
            for (int l = 0; l < leftSize; l++) {
                for (int r = 0; r < rightSize; r++) {
                    if (c == '+') {
                        result[(*returnSize)++] = leftResults[l] + rightResults[r];
                    } else if (c == '-') {
                        result[(*returnSize)++] = leftResults[l] - rightResults[r];
                    } else if (c == '*') {
                        result[(*returnSize)++] = leftResults[l] * rightResults[r];
                    }
                }
            }
            
            free(left);
            free(right);
            free(leftResults);
            free(rightResults);
        }
    }
    
    // Base case: if no operator found, it's a number
    if (*returnSize == 0) {
        result[0] = atoi(expr);
        *returnSize = 1;
    }
    
    return result;
}

int* solution(char* expression, int* returnSize) {
    return compute(expression, returnSize);
}

int main() {
    char expression[21];
    fgets(expression, sizeof(expression), stdin);
    expression[strcspn(expression, "\n")] = 0;
    
    int returnSize;
    int* result = solution(expression, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4ⁿ/n^1.5)

Catalan number of ways to parenthesize, approximately 4^n divided by n^1.5

✓ Linear Growth

Space Complexity

O(4ⁿ/n^1.5)

Recursion depth and storage for all possible results

⚡ Linearithmic Space

185.0K Views

Medium Frequency

~25 min Avg. Time

3.4K 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

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler