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

The Binomial Coefficients are defined as follows: B( n, k ) = 1 if k=0 or k=n, and B(n, k) = B(n - 1, k - 1) + B(n - 1, k) otherwise. Write a recursive method to compute the binomial coefficients and use it to output B(14,3), B(14,11), and B(18,8).

Part II

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 III

Write a program that reads numbers DIRECTLY from this URL http://www.cs.fiu.edu/~weiss/cop3804/assignments/assign4c.txt 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 )