CareerCup

Its a variation on integer partition:
en.wikipedia.org/wiki/Partition_(number_theory)

And code to generate partitions here:
chinmaylokesh.wordpress.com/2011/01/26/partition-number-theory-ferrers-diagram/

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);
}

#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;
}

Just to clarify the question,

shouldn't 6 be,
6 --> { [6], [4,2], [3,3], [2,2,2] }

maybe to solve it , I think we need DP.

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)))

public class a {
	static void print(int i,String prefix,int min){
		 System.out.println(prefix +i);
		 if(min==0)	min=2;
		 for(int j=min;j<=(i-j);j++)
			 print(i-j,prefix+j,j);
	}

	public static void main(String[] args) {
		print(18,"",0);
	}
}

def gensum_helper(s,t):
   if t<=0:
       yield [s]
   else:
      for i in range(s,t+1):
          for j in gensum_helper(i,t-i):
              yield [s] + j

def gensum(n):
  for i in range(1,n+1):
      for j in gensum_helper(i,n-i):
          yield j

#test
for i in gensum(8):
    print(i)