Medium · Backtracking

Different Ways to Add Parentheses

Given a string expression made of non-negative integers and the operators '+', '-' and '*', return the value of the expression under every way of fully parenthesizing it (one value per grouping, duplicates included), in any order.

Examples

Example 1

{
  "expr": "2-1-1"
}

Output: 2 values

Example 2

{
  "expr": "2*3-4*5"
}

Output: 5 values

Rebuild it in the studio

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.