There are many ways to approach this problem. An elegant solution should be able to provide an answer in linear time - if your code is not finishing executing for large inputs, you may want to step back and do an analysis of your algorithm. If you are stuck, trying some small examples with pen and paper should give you a good start.

To receive credit for this assignment, please read the following carefully:

Your program will be compiled, run, and tested by an automatic grading script, so any compilation failures will result in a zero. As such,

The source code should not contain any package statements.

Your program should read input from standard in (System.in) and print the correct response to the console (System.out).

Do not print out any human-centric messages. Output should be printed exactly as described in the Output section of the attached file.

Instead of printing "The result is: 2", just print "2"

Submit Java source code with the file name formatted as Lastname_Firstname_Problem02.java

Any preconditions set by the problem description will be met. No input validation is needed.

Ex: Your program will not have to check that "2

Seemingly Simple Subsets Recall that by definition, a set S is said to be a subset of another set U if and only if the intersection. SnU = S. For instance, the set S = {1,2) is a subset of U = {1, 2, 3, 4} as the elements 1, 2 S are also elements of U, hence the intersection of the two sets is S. Take notice that our definition of a set is not restricted to a proper subset, that is for any set U, U CU and that our definition of subset implies that the empty set is a subset of every set. Recall also that the cardinality, or size, of a set S, denoted S, is defined as the number of elements contained within the set. For example, the set {4,1,2) has cardinality 14. 1.2 = 3. Your task is simple: given a set, output the number of subsets of a certain cardinality As a hint, consider tlh To iterate is human, to recurse, divine -L. Peter Deutsch Input Input will consist of two lines. The first ne wil be a set U (2 s IU 15) of comma seperated integers (no spaces after commas) surrounded by brackets. The second line will contain a single integer n Output You are to output a single integer representing the number of subsets of U with car dinality n. More formally, you are to output the integer l(S U : |s| = n}| Sample Output 1 Sample Input 1 11,2,3) Sample Input 2 11,2,3,4) Sample Input 3 11, 2,3, 4,5, 6) Sample Input 4 Sample Output 2 Sample Output 3 Sample Output 4 1, 2,3, 4,5,6) 0