Sum Problem

Node.java

package me.nrubin29.sumproblem;

import java.util.ArrayList;

public class Node implements Comparable<Node> {

	private int value;
	private ArrayList<NodePair> children;
	
	public Node(int value) {
		this.value = value;
		this.children = new ArrayList<>();
	}
	
	public int getValue() {
		return value;
	}
	
	public void addChild(NodePair child) {
		children.add(child);
	}
	
	public NodePair[] getChildren() {
		return children.toArray(new NodePair[children.size()]);
	}
	
	@Override
	public boolean equals(Object o) {
		return this == o;
	}
	
	@Override
	public int compareTo(Node o) {
		return Integer.compare(value, o.getValue());
	}
	
	@Override
	public String toString() {
		return "Node value=" + value;
	}
}

NodePair.java

package me.nrubin29.sumproblem;

public class NodePair {

	private Node left, right;
	
	public NodePair(Node left, Node right) {
		this.left = left;
		this.right = right;
	}
	
	public Node getLeft() {
		return left;
	}
	
	public Node getRight() {
		return right;
	}
	
	public Node getOther(Node node) {
		if (node == left) {
			return right;
		}
		
		else if (node == right) {
			return left;
		}
		
		else {
			return null;
		}
	}
	
	public Node[] getNodes() {
		return new Node[] { left, right };
	}
	
	@Override
	public String toString() {
		return "NodePair left={" + left + "} right={" + right + "}";
	}
}

SumProblem.java

package me.nrubin29.sumproblem;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class SumProblem {

	/*
	The following code was written in 42 minutes. You have been warned.
	 */
	public static void main(String[] args) {
		for (String summation: getSums(15)) {
			System.out.println(summation);
		}
	}
	
	public static List<String> getSums(int n) {
		ArrayList<Node[]> sumGroups = new ArrayList<>();
		
		Node root = new Node(n);
		addChildren(root);
		
		for (Node[] sumGroup: getSumGroups(root, new Node[0])) {
			boolean unique = true;
			
			for (Node[] otherGroup: sumGroups) {
				if (Arrays.equals(mapToInts(sumGroup), mapToInts(otherGroup))) {
					unique = false;
					break;
				}
			}
			
			if (unique) {
				sumGroups.add(sumGroup);
			}
		}
		
		return sumGroups.stream().map(nodeArray -> join(" + ", nodeArray)).collect(Collectors.toList());
	}
	
	private static void addChildren(Node parent) {
		for (int i = 1; i < parent.getValue(); i++) {
			Node left = new Node(i);
			Node right = new Node(parent.getValue() - i);
			
			parent.addChild(new NodePair(left, right));
			
			addChildren(left);
			addChildren(right);
		}
	}
	
	private static ArrayList<Node[]> getSumGroups(Node node, Node[] stack) {
		ArrayList<Node[]> sumGroups = new ArrayList<>();
		
		for (NodePair pair : node.getChildren()) {
			Node[] newGroup = new Node[stack.length + 2];
			newGroup[0] = pair.getLeft();
			newGroup[1] = pair.getRight();
			
			for (int i = 2; i < newGroup.length; i++) {
				newGroup[i] = stack[i - 2];
			}
			
			Arrays.sort(newGroup);
			
			boolean unique = true;
			
			for (int i = 0; i < newGroup.length - 1; i++) {
				if (newGroup[i].getValue() == newGroup[i + 1].getValue()) {
					unique = false;
					break;
				}
			}
			
			if (unique) {
				sumGroups.add(newGroup);
			}
			
			for (Node child: pair.getNodes()) {
				boolean uniqueInStack = true;
				
				for (Node other: stack) {
					if (other.getValue() == child.getValue()) {
						uniqueInStack = false;
					}
				}
				
				if (uniqueInStack) {
					sumGroups.addAll(getSumGroups(child, add(stack, pair.getOther(child))));
				}
			}
		}
		
		return sumGroups;
	}
	
	private static Node[] add(Node[] array, Node value) {
		Node[] joined = new Node[array.length + 1];
		joined[0] = value;
		
		for (int i = 1; i < joined.length; i++) {
			joined[i] = array[i - 1];
		}
		
		return joined;
	}
	
	private static String join(String delim, Node[] array) {
		String output = "";
		
		for (int i = 0; i < array.length - 1; i++) {
			output += array[i].getValue() + delim;
		}
		
		output += array[array.length - 1].getValue();
		
		return output;
	}
	
	private static int[] mapToInts(Node[] array) {
		int[] ints = new int[array.length];
		
		for (int i = 0; i < array.length; i++) {
			ints[i] = array[i].getValue();
		}
		
		return ints;
	}
}