Assignment #3b, COP-3530

Do Exercise 7.24. A sketch of an algorithm is provided below.

The Routines

Provide two static methods getSubset with the following signatures: 
public  static int [ ] getSubset( int [ ] arr, int sum )
private static List    getSubset( int [ ] arr, int sum, int low, int high )
The first version returns an array of elements that are contained in arr and whose sum is sum. If no such subset exists, then the return value is null. Note that if sum is 0, then the return value is an array of length 0. The second version returns a List (you may use either ArrayList or LinkedList as the actual returned object, but the static return type remains List) of Integer elements, using only items in the subarray arr[low...high], whose sum is sum. It should be a simple matter to implement the first version of getSubset by making a call to the second version. The second version is the recursive algorithm that will be described below. Provide a main that tests the cases below, by making calls to the public getSubset and either outputting the matching sequence or an indication that there is no match.

The Recursive Algorithm

Recall that the method signature is 
private static List getSubset( int [ ] arr, int sum, int low, int high )
Here are the basic cases:

Base Case

If low>high, then there is no element in the subarray, and getSubset should return an empty list if sum==0, and null otherwise.

Recursive Case

Otherwise there is one or more element. In that case, there is a matching sequence if either of the following cases is true:
  1. getSubset( arr, sum,              low+1, high ) is true
  2. getSubset( arr, sum - arr[ low ], low+1, high ) is true
The first case says that there is a match using elements in positions low+1 to high The second case says that there is a match using element arr[low] plus other elements in positions low+1 to high. In the second case, arr[low] is one of the elements that will be part of the match and can be included in the returned List.

What to Submit

Place your source code in a single file. The whole program should fit in about a page. Submit your source code and run on the data sets below.

Data Sets

The first two sets are guaranteed to have matches for any value of sum (that is not too large). The third set is not.

Powers of 2

Input array: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536.
sum: 100000

Fibonacci Numbers

Input array: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946.
sum: 12000

Nothing Special

Input array: 2134, 5436, 8796, 6578, 1234, 9999, 4534, 1492, 1996, 1997, 3859, 3337, 3530, 1999, 6405.
sum: 11000; sum: 12000; sum: 13000; sum: 14000;