Assignment #3: Subset Sums

This assignment has two parts; both can be solved by using recursion. I will provide some test cases prior to the due date.

Part I: Computing all Subset Sums

Given an array containing some integers (there may be duplicates), write a routine that returns all the possible sums that can be formed by using numbers in the array. For instance, if the array contains 4 and 6, the possible sums are 0, 4, 6, and 10. If the array contains 1, 3, 5, and 7, the possible sums are 0, 1, 3, 5, 7, 4, 6, 8, 8, 10, 12, 9, 11, 13, 15, and 16. Notice that 8 appears twice in the answer (1+7 and 3+5).

Part II: Reversing the Subset Sums

Given an array containing the possible sums, extract the original array of numbers (in other words, do Part I in reverse). You may assume there are no negative numbers. For this routine it will be very helpful to use a Multiset. A Multiset stores items but allows duplicates. Begin by implementing an efficient multiset class, by using a TreeMap (with the values representing counts) as the data member. Your multiset will need the following operations: clear, isEmpty, size, add, contains, findMax, findSecondSmallest, remove (which removes one instance, so if there are several duplicates, only one of them is removed), toString, and toArray.

Signatures

For both Part I and Part II, you must provide two public static methods that take a single int[] as parameter and return a single int[]. You may write private methods that have additional parameters, different types of parameters (for instance multisets), etc., but the public signatures must use arrays.

Relationship to Course Outcomes