Assignment #2: Recursion

It is possible to do all three parts 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

Implement a method, containsSum returns true if some subset of numbers in items sum to exactly K and false otherwise. For instance if the input list items contains 1, 7, 10, and 12, and K is 20, the call returns true (1+7+12). But if K is 21, the call returns false.

Part III

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 )