Write a program called SubsetTarget in Java that reads in a text file, in.txt, that contains a list of positive and negative integers (duplicates are possible) separated by spaces. Zero may be included. You should read the integers into a singly linked list in the same order in which they appear in the input file. In other words, you may not rearrange the integers as you read them in nor may you rearrange them after you have read them in. The singly linked list must remain immutable throughout the programs run after reading in the integers. Your program should print YES if there exists two subsets of integers such that the individual sum of the subsets are equal to a value in the other subset. All integers must be used and can only belong to a single subset but not both at the same time. If there are no such subsets then only print NO.

There may be several subset splits that result in a YES. Your program should only print a single YES or NO.

Examples

If in.txt contains 1 6 -2 -5 3 2, the program must print YES. The two subsets are the following

{1, 2} with sum 3 and {6, -2, -5, 3} with sum 2. Sum 3 is found in subset 2 while sum 2 is found in subset 1.

If in.txt contains 1 2 3 6, the program must print NO. You may notice that subset1 { 1, 2, 3} has sum 6 and is in subset2 but subset2 { 6 } has sum 6 but is not found in subset1.

If in.txt contains 5 -5 5 -5,the program must print NO. There are no two subsets such that their sums are values in the other subset.

Ifin.txt contains 5 6 2 -4 -7 4, the program must print YES.

{5, -7, 4} with sum 2 and {6, 2, -4} with sum 4. Sum 2 is within the second subset and sum 4 is within the first subset.

If in.txt contains -1 2 5 3 -2, the program must print YES. Subsets are

{-1, 5, -2} with sum 3 and {2, 3} with sum 5.

If in.txt contains 1 0 -1 0, the program must print NO.

If in.txt contains 1 0 -1 0 1, the program must print YES. Subsets are

{1, 0, 0} with sum 1 and {1, -1} with sum 0.

If in.txt contains 0, the program must print NO. Even though one subset will contain { 0 } with sum 0 the other subset is empty and contains no values to compare to.

Keep in mind that you only need to print YES or NO. Do not print the subsets or additional information. Doing so will result in points taken off as not a solution for the problem being asked. Any prints used for debugging should be removed before submitting.

Program Specification

Your program has to

Implement a singly linked list.

You must implement the linked list from scratch without using language libraries. For example, you are not allowed to use any built-in dynamic data structures, such as ArrayList or LinkedList. There is no need to provide a full-fledged implementation of a linked list. Keep your linked list implementation minimal and implement as much as you need to solve the problem. Each node of the linked list must include only two elements: an integer and a reference to the next element from the list.

Read the integers from the file in.txt and store them into the linked list in the same order in which they appear in the input file. Your list must remain immutable after reading in the elements and no processing on the elements while reading them from the text file may occur. At this point in the program the only operation should be reading in the numbers into the list.

Work on the linked list in order to find out if there exists two subsets such that their respective sums is equal to some value in the other subset. No additional data structures are allowed. All computations must be done in place on the original linked list. Your program must use only one data structure (and only one instance of it), the linked list, some auxiliary scalar variables and reference variables (used to point to different nodes of the list). No additional data structures are allowed, such as a second linked list, an array, strings, etc. If you have questions regarding this then feel free to email me.

The only exception to this is I/O where you can use strings to read in.txt. You can use standard I/O libraries to perform I/O. For example, you can use StringTokenizer or Scanner. This is the only place you can use strings and libraries.

Print YES or NO if such subsets exist.

No modification of the linked list. It must remain immutable after integers are read into it.

NOTE 1: Assignment 2 must be solved by working on the linked list. Bypassing the assignment restrictions as laid out above by saving numbers in a string or array or any other structure is not allowed and will be penalized. There must be only one instance of the list and it must not be changed.

NOTE 2: Using an integer as a binary mask to store information about subset membership is not a solution since fixed length binary masks cannot handle lists of arbitrary length.

Pack your code into one .java file. Inner classes are allowed. The program must be able to run with all code in one file. Syntax errors will result in heavy penalties. Try to write simple and short programs. I/O, exception handling, and the linked list implementation should be kept to a minimum. You can assume that the input is correct and that in.txt will contain at least one number and is in the same folder as your Java program.