## 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

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use 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++;

}...

By purchasing this solution you'll be able to access the following files:

Solution.zip.