import java.util.HashMap;
import java.util.List;
import java.util.LinkedList;

class Person {
	private String _name;
	private int _amount;
	public Person(String name, int amount) {
		_name = name; _amount = amount;
	}
	public String getName() { return _name; }
	public int getAmount() { return _amount; }
}

public class Combinations {
	public void findAllPairsDistinctAmounts(List<Person> people, int targetAmount) {
		HashMap<Integer, String> map = new HashMap<Integer, String>();
		for (Person currPerson : people) {
			int currAmt = currPerson.getAmount();
			String currName = currPerson.getName();
			String otherName = map.get(targetAmount - currAmt);
			if (otherName != null)
				System.out.println(
					"(" + otherName + ", " + currName + ")");
			map.put(currAmt, currName);
		}
	}
	
	public void findAllPairs(List<Person> people, int targetAmount) {
		HashMap<Integer, LinkedList<String>> map =
			new HashMap<Integer, LinkedList<String>>();
		for (Person currPerson : people) { // build HashMap and chains
			int currAmt = currPerson.getAmount();
			String currName = currPerson.getName();
			LinkedList<String> names = map.get(currAmt);
			if (names == null) {
				names = new LinkedList<String>();
				map.put(currAmt, names);
			}
			names.addLast(currName);
		}
		for (Person currPerson : people) { // find matches to curr person
			int currAmt = currPerson.getAmount();
			String currName = currPerson.getName();
			LinkedList<String> names = map.get(targetAmount - currAmt);
			if (names != null)
				for (String otherName : names)
					System.out.println(
						"(" + currName + ", " + otherName + ")");
			map.get(currAmt).remove(currName); // eliminate symmetry
		}
	}
	public static void main(String[] args) {
		LinkedList<Person> people = new LinkedList<Person>();
		people.addLast(new Person("Alice", 4));
		people.addLast(new Person("Bob", 3));
		people.addLast(new Person("Charlie", 7));
		people.addLast(new Person("Kenneth", 5));
		people.addLast(new Person("Victor", 2));
		Combinations program = new Combinations();
		program.findAllPairsDistinctAmounts(people, 9);
		/*
		people.addLast(new Person("James", 4)); // for part (b)
		people.addLast(new Person("Ivan", 5));
		program.findAllPairs(people, 9);
		*/
	}
}