## Question

The program has to do the following:

1. Implement the linked list without using any language libraries or any built-in dynamic data structures. Keep the linked list implementation minimal and implement enough needed to solve the problem. Each node of the linked list must include two elements, an integer and a reference to the next element from the list.

2. Read the integers from the text file. No calculations are allowed at this step. The program only reads the input numbers and stores them into the linked list.

3. Work on the linked list to find out the size of the largest zero-sum subset. No additional data structures are allowed. All computations are completed in place on the original data structure, which is the linked list. Some auxiliary scalar variables and reference variables can be used to point to different nodes on the list. Do not use an array or strings. The only exception is I/O libraries to perform I/O, for example StringTokenizer or scanner.

4. Print the size of the largest zero sum subset.

5. Do not modify the linked list, it should remain in its original form as it was read from the input file.

Additional notes:

- Using an integer as a binary mask to store data about subset membership is not allowed. A fixed length binary mask is not able to handle lists of arbitrary length.

- Provide a brief explanation of how the algorithm works using pseudo-code.

Zero sum subset examples:

The text file contains 4 -2 6, the program should print out 0. There is not a subset of integers where the sum is 0.

The text file contains 4 -1 3 1 -4. The zero sum subsets are (4, -4); (-1, 1); (4, 1, -4, -1). The largest zero sum subset is (4, 1, -4, -1) and the size is 4.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

public class ZeroSumLinkedList {class Node{

int data;

Node next;

}

int size;

Node head;

public ZeroSumLinkedList()

{

head = null;

size = 0;

}

public void add(int data)

{

Node node = new Node();

node.data = data;

node.next = null;

if(head == null)

{

head = node;

}

else

{

Node temp = head;

for(int i = 0; i < size-1; i++)

temp = temp.next;

temp.next = node;

}

size++;

}...