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.
[…] to a given number. so for example, if the user enters 6, the program should display >> 6… [full post] rahulj51 Miles to code uncategorized 0 0 0 0 0 […]