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.

Part III [extra credit]

Implement the reversing algorithm, but allow negative numbers. Use the following algorithm sketch:
  1. If none of the numbers are zero, there is no solution.
  2. If none of the numbers are negative, you can use the algorithm in Part II.
  3. If none of the numbers are positive, make them positive, use the algorithm in Part II, and then negate those results.
  4. Otherwise, there are some positive numbers and some negative numbers. Let x and y be the two largest numbers in the array of sums. Then either y-x or x-y is one of the original numbers (why??).
    1. Try y-x using the basic algorithm logic in Part II, and if that leads to a solution you are done.
    2. Otherwise, try x-y and if that leads to a solution you are done. Otherwise, there are no solutions.

Part IV [double extra credit]

Implement the reversing algorithm in the case of negative numbers and produce ALL solutions (return an array of arrays). For instance, it is easy to check that [ -1 -1 1 2 ] and [ -2 1 1 1 ] generate the same set of sums: [ -2 -1 -1 -1 0 0 0 0 1 1 1 1 2 2 2 3 ].

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