Algorithm practice – Possible addition combinations for any given number

I came across this interesting puzzle today on stackoverflow. Basically, the problem is to display all possible combinations of additions that can sum up to a given number. so for example, if the user enters 6, the program should display

>> 6

0+6=6
1+1+1+1+1+1=6
1+1+1+1+2=6
1+1+1+3=6
1+1+4=6
1+5=6
2+1+1+1+1=6
2+1+1+2=6
2+1+3=6
2+4=6
3+1+1+1=6
3+1+2=6
3+3=6
4+1+1=6
4+2=6
5+1=6
6+0=6


This is a classic recursion problem. Here’s my solution in Java.

	public void run(int n)
	{

		List<StringBuilder> combos = showAdditionsFor(n);
		
		for (StringBuilder s : combos)
		{
			if (s.indexOf("+") < 0)
			{
				System.out.println(s + " + 0 = " + n);
				System.out.println("0 + " + s + " = " + n);
			}
			else
			{
				System.out.println(s + " = " + n);
			}
		}
	}
	
	List<StringBuilder> showAdditionsFor(int n)
	{
		List<StringBuilder> list = new ArrayList<StringBuilder>();
		if (n == 0)
			list.add(new StringBuilder(""));
		else if (n == 1)
			list.add(new StringBuilder(String.valueOf(1)));
		else
		{
			for (int i = 1; i <=n; i++)
			{
				//get n-i list
				List<StringBuilder> tempList = showAdditionsFor(n-i);
				appendToEachListElement(String.valueOf(i),tempList);
				list.addAll(tempList);
			}
		}
			
		return list;
	}
	
	
	private void appendToEachListElement(String x, List<StringBuilder>l)
	{
		for (StringBuilder s : l)
		{
			if (s.length() == 0)
				s.append(x);
			else
				s.append("+" + x);
		}
	}

My program creates a list of all possible combinations as Strings. For input=6, it prints all possible combinations as follows.


1+1+1+1+1+1 = 6
2+1+1+1+1 = 6
1+2+1+1+1 = 6
3+1+1+1 = 6
1+1+2+1+1 = 6
2+2+1+1 = 6
1+3+1+1 = 6
4+1+1 = 6
1+1+1+2+1 = 6
2+1+2+1 = 6
1+2+2+1 = 6
3+2+1 = 6
1+1+3+1 = 6
2+3+1 = 6
1+4+1 = 6
5+1 = 6
1+1+1+1+2 = 6
2+1+1+2 = 6
1+2+1+2 = 6
3+1+2 = 6
1+1+2+2 = 6
2+2+2 = 6
1+3+2 = 6
4+2 = 6
1+1+1+3 = 6
2+1+3 = 6
1+2+3 = 6
3+3 = 6
1+1+4 = 6
2+4 = 6
1+5 = 6
6 + 0 = 6
0 + 6 = 6


The program could also be further refined to eliminate duplicate combinations by using Sets instead of StringBuilders.

I have also decided to eliminate the combination with 0 in the calculation logic because it adds ambiguities to the solution (as this answer points out). Instead I am handling this case by brute force in the run method.

Advertisement