Description
Given a sequence of numbers and a single target number, construct a valid arithmetic expression
by combining numbers from the sequence using addition, subtraction, multiplication, division and parentheses,
and such that the result of evaluating the expression is the target number.
A valid expression should satisfy the following conditions:
- Each number from the sequence can only be used once in the expression.
- It is not required to use all values from the sequence.
- All intermediate values must be positive natural numbers (1, 2, 3, etc). The use of negative numbers, zero and fractions are not permitted. Expressions like these should not appear in the valid expression: 2/3, (1-2), (1+2)-3.
Performance of the solution can be checked on the following input:
- A set of 7 numbers [3, 19, 45, 21, 10, 4, 7]
- A target number is 100
Solution
C# Implementation - Open on Github
References
- Graham Hutton. Functional Pearl. The countdown problem
- Catalan Number