Assignment #4: Recursion

It is possible to do both Part I and Part II without using recursion, but it would be VERY HARD. With recursion, the amount of code is minimal.

Part I

A non-contiguous substring of String s is a sequence of k >= 0 characters in s, in the order in which they occur in s. For instance, the following table shows ALL the non-contiguous substrings of some String s.
String s        All non-contiguous substrings of s
========        ==================================
""              ""
"a"             "" "a"
"ab"            "" "a" "b" "ab"
"abc"           "" "a" "b" "ab" "c" "ac" "bc" "abc"
Write a routine generateAll that returns an ArrayList containing all the non-contiguous substrings of parameter s, and test it on "abcde".

Part II

Write a program that reads numbers from a file (presumably there are only a few numbers in the file) and outputs all the possible sums that can be formed by subsets of the numbers. For instance, if the numbers in the file are 3 4 6, then the output would be 0, 3, 4, 6, 7, 9, 10, 13. Note that 0 is in the output because it uses none of the numbers, while 13 uses all of the numbers. Central to writing this program is implementing the method:
// Return all sums that can be formed from subsets of elements in arr
public static ArrayList<Integer> allSums( ArrayList<Integer> arr )