CareerCup

void intpart(string pref, int n, int maxi){
	if(n==0){
		cout << pref << endl;
		return;
	}
	for(int i=1; i<=maxi && i<=n; i++)
		intpart(pref+(pref==""?"":"+")+to_string(i), n-i,i);
}

int main(){
	int n=10;
	intpart("", n, n);
	return 0;
}

public static void all(int t){
	String R[][] = new String[t+1][];
	R[0] =new String[0];
	for(int i = 1; i <= t; i++){
		R[i] = new String[(i/2) + 1];
		for( int j = 1; j <= i/2; j++){
			R[i][j] = (i-j) + "+" + j + "";
		}
	}
	System.out.println(" -> ["+t+"] =  ");
	for(int i = t; i >= 0 ; i-- ){
		for(int j = 1; j < R[i].length; j++){
			System.out.print(R[i][j]);
			for(int x= i; x < t; x++){
				 System.out.print("+1");
			}
			System.out.print(", ");
			
		}
		System.out.println();
	}
	System.out.println();
}

test case:

all(10);

output:

-> [10] =
9+1, 8+2, 7+3, 6+4, 5+5,
8+1+1, 7+2+1, 6+3+1, 5+4+1,
7+1+1+1, 6+2+1+1, 5+3+1+1, 4+4+1+1,
6+1+1+1+1, 5+2+1+1+1, 4+3+1+1+1,
5+1+1+1+1+1, 4+2+1+1+1+1, 3+3+1+1+1+1,
4+1+1+1+1+1+1, 3+2+1+1+1+1+1,
3+1+1+1+1+1+1+1, 2+2+1+1+1+1+1+1,
2+1+1+1+1+1+1+1+1,
1+1+1+1+1+1+1+1+1+1,

Here in the complexity, I need help. It seems that It is n^3 worse case ( but not sure )
Complexity

O ( n* n/2) + O (n*(n/2)*t) = O (n^2) ??? please help.

A little improvement on my previous approach. But It still O (n^3)

Is there any better way to improve this ?

public static void printAll(int t){
 		System.out.println(t + " = ");
 		for(int i=2; i <= t; i++){
 			for(int j=1; j <= i/2 ; j++){
 				System.out.print((i-j) + "+" + j);
 				for(int x=i; x < t; x++){
 					System.out.print("+1");
 				}
			System.out.println();	 			
 			}
 		}
 	}

Look up the rod partition problem in CLRS.

import sys

if len(sys.argv) < 2:
        exit(1)

T = int(sys.argv[1])

def getSum(t):
        l = [[1,1]]
        for i in xrange(3, t+1):
                for j in xrange(len(l)):
                        l[j].append(1)
                for j in xrange(1, int(i/2)+1):
                        l.append([j, i-j])
        return l
for l in getSum(T):
        for n in l:
                print n,
        print ""

It's in o(n^2)

public class PrintNumbers {

static int n = 13;

public static void main(String[] args) {

for (int i = 1; i < n; i++) {
int k = n / i;
StringBuilder sb = new StringBuilder("");
for (int j = 1; j <= k; j++) {
if (j == 1) {
sb.append(i);
} else {
sb.append(" + " + i);
}
}
if (i * k < n) {
display(n - (i * k), sb.toString());
} else {
System.out.println(sb.toString());
}
}
}

public static void display(int n, String str) {

for (int i = 1; i <= n; i++) {
StringBuilder sb = new StringBuilder(str);
int k = n / i;
for (int j = 1; j <= k; j++) {
sb.append(" + " + i);
}
if (i * k < n) {
display(n - (i * k), sb.toString());
} else if (i * k == n) {
System.out.println(sb.toString());
}

}
}
}


Output number T=13

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
2 + 2 + 2 + 2 + 2 + 2 + 1
3 + 3 + 3 + 3 + 1
4 + 4 + 4 + 1
5 + 5 + 1 + 1 + 1
5 + 5 + 2 + 1
5 + 5 + 3
6 + 6 + 1
7 + 1 + 1 + 1 + 1 + 1 + 1
7 + 2 + 2 + 2
7 + 3 + 3
7 + 4 + 1 + 1
7 + 4 + 2
7 + 5 + 1
7 + 6
8 + 1 + 1 + 1 + 1 + 1
8 + 2 + 2 + 1
8 + 3 + 1 + 1
8 + 3 + 2
8 + 4 + 1
8 + 5
9 + 1 + 1 + 1 + 1
9 + 2 + 2
9 + 3 + 1
9 + 4
10 + 1 + 1 + 1
10 + 2 + 1
10 + 3
11 + 1 + 1
11 + 2
12 + 1

#include "stdafx.h"
#include "iostream"
#include "map"
#include "list"
#include <sstream>

using namespace std;
class Trick
{
public:
void showallcombinations(int a)
{
for (int i=1; i<=a; i++ )
{
setof2(i);
}
for (int i=2; i<=a-1; i++ )
{
//list <string> temp1 = mapofall[i];
for (std::list<string>::iterator it = mapofall[i].begin(); it != mapofall[i].end(); it++)
{
string tempStr = *it;
tempStr = tempStr + "+ 1";
mapofall[i+1].push_back(tempStr);
}
}
list <string> temp1 = mapofall[a];
for (std::list<string>::iterator it = temp1.begin(); it != temp1.end(); it++)
{
cout << *it << endl;
}
}
private:
int setof2(int a)
{
// i want find all set of 2 to get sum
list<string> locallist;
for (int i=1,j=a-1; i<=j; i++,j-- )
{
if ((i+j) == a)
{
// std::cout << i << "+" << j << std::endl;
stringstream si,sj;
si << i;
sj << j;
string tempStr = si.str()+"+"+sj.str();
locallist.push_back(tempStr);
}
}
mapofall[a] =locallist;
return 0;
}
std::map<int,list<string>> mapofall;
};

int _tmain(int argc, _TCHAR* argv[])
{
std::cout << "HELLO WORLD" << std::endl;
Trick obj;
obj.showallcombinations(10);
int i;
std::cin >> i;
return 0;
}

Output:: [10]
2+8
3+7
4+6
5+5
1+8+ 1
2+7+ 1
3+6+ 1
4+5+ 1
1+7+ 1+ 1
2+6+ 1+ 1
3+5+ 1+ 1
4+4+ 1+ 1
1+6+ 1+ 1+ 1
2+5+ 1+ 1+ 1
3+4+ 1+ 1+ 1
1+5+ 1+ 1+ 1+ 1
2+4+ 1+ 1+ 1+ 1
3+3+ 1+ 1+ 1+ 1
1+4+ 1+ 1+ 1+ 1+ 1
2+3+ 1+ 1+ 1+ 1+ 1
1+3+ 1+ 1+ 1+ 1+ 1+ 1
2+2+ 1+ 1+ 1+ 1+ 1+ 1
1+2+ 1+ 1+ 1+ 1+ 1+ 1+ 1
1+1+ 1+ 1+ 1+ 1+ 1+ 1+ 1+ 1