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:
-
getSubset( arr, sum,
low+1, high ) is true
-
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;