Every way to bracket a sum
List every value an expression can take if you may add brackets anywhere, by trying each operator as the last one to apply. About 20 minutes.
Pick the last operation
In 2-1-1 you can bracket it as (2-1)-1 = 0 or 2-(1-1) = 2. Different bracketings give different values. How many different values can appear, and what are they?
Pick any operator and imagine it is the last one applied. Everything to its left is an expression of its own, and so is everything to its right, and both can be bracketed in any way. So the answers for that choice are every combination of a left answer with a right answer.
nums = [1, 2, 3]
for i in range(1, len(nums)):
left = nums[:i]
right = nums[i:]Make the first minus the last operation: the left part is 4, the right part is 2 - 1, which can only be 1. So 4 - 1 = 3.
Numbers are the base case
An expression without any operator is just a number, and that number is its one and only result. Everything else builds on it.
Keep duplicates in the result list: if two different bracketings give the same value, both are in the list. At the end the problem asks for the values in increasing order, so sort the final list once.
How many results does a single number like 7 have?
- AOne: [7]
- BNone
- CTwo
Show the answer
One: [7]. With no operator there is nothing to bracket.
Every way to bracket
expr is an arithmetic expression made of non-negative whole numbers (at most 99) joined by the operators +, - and *, with no spaces. You may put brackets anywhere. Return a sorted list of the value of every different way to bracket the expression (a value appears once per bracketing, so repeated values are repeated in the list).
expr = "2-1-1" → [0, 2]
1 ≤ length ≤ 13 · the number of bracketings is at most 1,430