CSC220 Project 1
Due: 11:59PM, Tuesday, November 3

Your task is to write a code for solving the following formula calculation problem.

Given some integers, called base integers, and another integer, called a target, decide whether it is possible to produce the target from the base integers by using each number exactly once and using only basic arithmetic operatons (+, -, *, and /) and, if so, compute a formula that produces the target.

For example, given base integers 3, 3, 2, and 5 and target 2, the answer to the decision problem is in the affirmative and the answer to the subsequent computational problem can be (3+3)/(5-2). On the other hand, for the same base numbers and for target 22, the answer to the decision problem is in the negative.

The decision problem can be solved using a recursive procedure (let's call it P for now) as follows:

• Input to P consists of an integer array A[0..m-1] of size m and an integer t.
• The procedure P answers, using a boolean return value, whether it is possible to produce t from base integers A[0], ..., A[m-1].
• If m is equal to 1, then the answer is simple.
• If m is greater than 2, then fix two indices i and j, and for each binary operation betwen A[i] and A[j] that produces an integer, decide whether replacing A[i] and A[j] with the outcome of the binary opration produces a set of base numbers that produces the target t.
• A crucial question in the above is, which i and j should be used.
This recursive procedure P solves only the decision problem and does not solve the subsequent computational problem. Your goal is to write a code that solves the decision problem but also the computational problem using recursion.
• This can be accomplished by expanding the input to P by adding an additional String array of size equal to the array A that show how the numbers in the array A are produced.
• A sample program can be found here.