Countdown Problem

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.
For example, given the sequence of source numbers [1, 3, 7, 10, 25, 50] and the target number 765, the expression (1 + 50) * (25 - 10) solves the problem.

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

Last updated: 28.10.2017,
created: 12.06.2017.