Command Palette

Search for a command to run...

Hectal
Problem 38.3 · Advanced Search and Divide & ConquerMedium

Different Ways to Add Parentheses

PatternDivide and ConquerRecursion

What it teaches: Split at every operator and combine every left result with every right result.

Practise it on judges as “Different Ways to Add Parentheses”.

In plain words

You have a sum like 2*3-4*5 and you may put brackets anywhere. Each operator could be the very last one done. Split at that operator, work out every possible answer for the left part and the right part, and combine each pair. Small parts repeat, so remember their answers.

Return every result (repeats included). Example: "2*3-4*5" → [-34, -14, -10, -10, 10].

The problem

Given an expression of numbers and +, −, *, return all results from every way of adding parentheses, in any order (duplicates included).

Example 1

Input: expression = "2*3-4*5"
Output: [-34, -14, -10, -10, 10]

Constraints

  • 1 ≤ length ≤ 20
  • Numbers 0–99

Pattern clues in the wording

  • → All groupings of an expression

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution · starter
import java.util.*;

class Solution {
    public List<Integer> diffWaysToCompute(String expression) {
        return new ArrayList<>();
    }
}

Write your solution locally or in your editor for now. Pick Java, Python, C++, JavaScript or Go above: every solution on this page switches with it. The in-browser runner will run these tests right here.

Test cases

#InputExpected
1
expression = "2-1-1"
[0,2]
2
expression = "2*3-4*5"
[-34,-14,-10,-10,10]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Recursive split with memo · Catalan-number output size
1

Recursive split with memo

Time Catalan-number output size Space Memo of substrings

For each operator, combine all results of the left and right substrings. A string without operators is a number.

▶ Dry run: Split at each operatorexpression = "2*3-4*5"
2
0
*
1
3
2
-
3
4
4
*
5
5
6

parts(map)

2: [2]3-4*5: [3-20 = -17, (3-4)*5 = -5]

out(list)

-34-10

Step 1/4Last operation is the first *: left 2, right "3-4*5" has two answers (-17, -5). 2 × -17 = -34, 2 × -5 = -10.

Approach 1
import java.util.*;

class Solution {
    private final Map<String, List<Integer>> memo = new HashMap<>();

    public List<Integer> diffWaysToCompute(String expression) {
        if (memo.containsKey(expression)) return memo.get(expression);
        List<Integer> out = new ArrayList<>();
        for (int i = 0; i < expression.length(); i++) {
            char op = expression.charAt(i);
            if (op != '+' && op != '-' && op != '*') continue;
            for (int a : diffWaysToCompute(expression.substring(0, i)))
                for (int b : diffWaysToCompute(expression.substring(i + 1)))
                    out.add(op == '+' ? a + b : op == '-' ? a - b : a * b);
        }
        if (out.isEmpty()) out.add(Integer.parseInt(expression));
        memo.put(expression, out);
        return out;
    }
}

Verdict: Same split structure as interval DP.

Before you submit

Edge cases and common mistakes

Test these inputs

  • Single number
  • Two-digit numbers

Mistakes people make

  • Splitting inside multi-digit numbers.

Interview

Follow-up questions

How many results are there for k operators?