## Amazon Interview Question Software Engineer / Developers

- 0of 0 votes
Given an integer (assume it's smaller than 50), write an algorithm that will generate all possible combinations of integers greater than 1 and they produce a sum equals to this number. The same number can appear more than once in a combination. What's the time complexity of your algorithm?

For example:

<=1 -> {}

2 -> {2},

3->{3},

4->{[4], [2, 2]},

5->{[5], [3, 2]},

6->{[6], [4, 2], [3, 3], [2, 2, 2]}

7->{[7], [5, 2], [4, 3], [3, 2, 2]}

8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}

....

**Country:**United States

```
public class Partition {
public static List<String> partition(int n) {
List<String> partitions = new ArrayList<String>();
partition(n, n, "", partitions);
return partitions;
}
public static void partition(int n, int max, String prefix, List<String> partitions) {
if (n == 0) {
partitions.add(prefix);
return;
}
for (int i = Math.min(max, n); i > 1; i--) {
partition(n-i, i, prefix + " " + i, partitions);
}
}
public static void main(String[] args) {
for(String partition: partition(7)){
System.out.println(partition);
}
}
```

}

public void findSum(int num, ArrayList<Integer> list, HashSet<HashMap<Integer, Integer>> set)

1. If num == 1, return

2. If num == 0, build a hashmap which records each number in list and its corresponding frequency. If this map is contained in set, return; else add the map into the set, and print each element of the list

3. for(int i = 2; i <= num; ++i)

{

ArrayList<Integer> newList = (ArrayList<Integer>) list.clone();

newList.add(i);

findSum(num-i, newList, set);

}

Sorry, found two bugs:

1. should be if num == 1 || num < 0, return;

2. after print the list, a return statement should be added.

```
#include <stdio.h>
#include <iostream>
using namespace std;
int cont(int k){
int j = k/2;
if( k%2 == 0 ){
j = k/2-1;
}
return j;
}
int main( int argc, char *argv[] )
{
int j;
cin >> j;
if( j == 2 || j == 3 ){
printf("K: {%d}\n", j);
return 0;
}
int t = cont(j);
for( int k = j; k >= 2 && k > t; k-- ){
if( k == j ){
printf("K: {%d}\n", j);
} else {
if( j-k > 1 )
printf("K: {%d,%d}\n", j-k, k );
}
}
return 0;
}
```

Here is a recursive solution in java..i checked the solution till 8

public class combinations {

/**

* @param args

*/

int findcomb(int n)

{

if(n==0)

return 0;

for(int i=2;i<=n;i++)

{

if((n-i)>1||(n-i)==0)

{

System.out.print(i+" ");

findcomb(n-i);

}

}

System.out.println("\n");

return 0;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

combinations x=new combinations();

x.findcomb(12);

}

}

}}}

somewhat strange solution but it works. just using combination. not DP

not elegant.

```
#include <stdio.h>
#include <iostream>
using namespace std;
void print_array( int *b, int q, int sum ){
int tmp = 0;
for( int i = q-1; i >= 0; i-- )
{
tmp += b[i];
}
if( tmp == sum ) {
printf("[");
for( int i = q-1; i >= 0; i-- )
{
printf("%d ", b[i]);
}
printf("]\n");
}
}
void H_combi( int *a, int *b, int n, int r, int q, int sum )
{
if( r == 0 )
print_array(b, q, sum);
else if( n == 0 )
return;
else
{
if( a[n-1] == 0 ){
printf("n: %d, r: %d\n", n, r );
}
b[r-1] = a[n-1];
H_combi( a, b, n, r-1, q, sum );
H_combi( a, b, n-1, r, q, sum );
}
}
int main( int argc, char *argv[] ){
int num;
cin >> num;
if( num < 2 ){
return 0;
}
if( num == 2 || num == 3 ){
printf("[%d]\n", num);
return 0;
}
int maxsize = num / 2;
printf("[%d]\n", num);
for( int i = 2; i <= maxsize; i++ ){
int limit = num - (i-1)*2;
int *k = new int[limit-1];
for( int j = 2; j <= limit; j++ ){
k[j-2] = j;
}
int *r = new int[i];
H_combi( k, r, limit-1, i, i, num );
}
return 0;
}
```

```
def partitions(n):
if n<1:
yield ()
else:
for p in partitions1(n,n):
yield p
def partitions1(n,m):
#print "p1", (n,m)
assert m<=n
if n<1:
yield ()
else:
for i in range(1,m+1):
rem = n-i
m2 = min(i, rem)
for p in partitions1(rem, m2):
yield (i,)+p
def tp(n):
print ":::", n
for p in partitions(n):
print p
for i in range(7):
tp(i)
print
for i in range(35):
print i, len(list(partitions(i)))
```

Its a variation on integer partition:

- CameronWills on November 12, 2012 Edit | Flag Replyen.wikipedia.org/wiki/Partition_(number_theory)

And code to generate partitions here:

chinmaylokesh.wordpress.com/2011/01/26/partition-number-theory-ferrers-diagram/