Different Ways to Add Parentheses
Real-world version: Every Value a Sum Can Be Grouped IntoThe statement here is our own: the same inputs, outputs and technique.
An arithmetic line is given as expression, made of whole numbers and the signs '+', '-' and '*', with no spaces and no signs marking a number as negative.
Brackets may be put anywhere, so long as the result is a valid arithmetic line, which fixes the order the operations happen in. Different bracketings may give different values.
Return the values from every possible bracketing, in increasing order. A value appears as many times as there are bracketings producing it.
Examples
Example 1
- Input
- expression = "2-3-4"
- Output
- [-5, 3]
Bracketing the first subtraction gives minus five, and bracketing the second gives three.
Example 2
- Input
- expression = "99"
- Output
- [99]
There is no sign to bracket, so the line takes its own value.
Example 3
- Input
- expression = "1+1"
- Output
- [2]
One sign means one bracketing.
Constraints
- 1 <= expression.length <= 20
- expression consists of digits and the signs '+', '-' and '*' only
- Every whole number in expression is between 0 and 99
- No number in expression is marked with a leading sign
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def diff_ways_to_compute(expression: str) -> list[int]:public List<Integer> diffWaysToCompute(String expression)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's