Sunday, August 3, 2014

Number of ways to obtain a number n by adding numbers from 1 to n

Problem
Given a number n, find the different combinations of numbers from 1 to n, which can be added to obtain the number n.
Sample Input
5
Sample Output
1. 1,1,1,1,1
2. 1,1,1,2
3. 1,1,3
4. 1,2,2
5. 1,4
6. 2,3
7. 5
Java Code

import java.util.ArrayList;

public class Sum {
private static int count = 0;
public static void main(String[] args) {
ArrayList<Integer> array = new ArrayList<Integer>();
int n = 5;
long start = System.currentTimeMillis();
find(n,array,1);
long end = System.currentTimeMillis();
System.out.println("Time taken for " + n + " is " + (end - start) + " milliseconds.");
}
public static void find(int n, ArrayList<Integer> array,int start) {
int sum = 0;
for(int i=0;i<array.size();i++) {
sum += array.get(i);
}
if(sum == n) {
System.out.print(count + ".\t");
for(int i=0;i<array.size();i++) {
if(i != array.size() - 1) {
System.out.print(array.get(i) + ",");
}
else {
System.out.print(array.get(i));
}
}
System.out.println();
count++;
return;
}
else if(sum > n) {
return;
}
else {
for(int ele = start; ele <= n; ele++) {
if(sum + ele <= n) {
array.add(ele);
find(n,array,ele);
array.remove(array.get(array.size() - 1));
}
else {
break;
}
/*array.add(ele);
find(n,array,ele);
array.remove(array.get(array.size() - 1));*/
}
}
}
}