1. if the number can be divided into smaller repeatable numbers,
for number 6:
6
5+1
4+2 4+1+1
3+3 3+2+1 3+1+1+1
......
Algorithm:
public int split(int n,int m)
{
if (n<1 || m<1)
{
return 0;
}
if (n==1 | m==1)
{
return 1;
}
if(n<m)
{
return split(n,n);
}
if (n==m)
{
return split(n,m-1)+1;
}
return split(n,m-1)+split(n-m,m);
}
If you'd like to print every possibilities:
int[] map=new int[n];
private void print(int len)
{
if (len ==0)
{
return;
}
StringBuffer str=new StringBuffer(2*len);
for (int i=0;i<len-1 ;i++ )
{
str.append(map[i]+"+");
}
str.append(map[len-1]);
System.out.println(str.toString());
}
public int splitAndPrint(int n,int m,int len)
{
if (n == 0 && m == 1 )
{
print(len);
return 1;
}
else if ( n == 1 && m > 1)
{
map[len]=1;
print(len+1);
return 1;
}
else if (n >= 1 && m == 1)
{
map[len]=1;
splitAndPrint(n-1,m,len+1);
return 1;
}
else if(n<m)
{
return splitAndPrint(n,n,len);
}
else if (n==m)
{
map[len]=m;
print(len+1);
return splitAndPrint(n,m-1,len)+1;
}
map[len]=m;
int s1=splitAndPrint(n-m,m,len+1);
int s2=splitAndPrint(n,m-1,len);
return s1+s2;
}
2. if the divided numbers must be not repeatable:
5+1
4+2
3+2+1
Algorithm:
long map=new long[n];
public long split2AndPrint(long n,long m,int len)
{
if(n==1 || n==2 )
{
return 0;
}
long s=0;
for (long i=n-1; i>= 1; i--)
{
if(i>=m)
continue;
// can be optimized further
if(i*(i+1)<2*n)
break;
map[len]=i;
long min=m;
if(min>i) min=i;
if(min>(n-i)) min=n-i;
if((n-i)<i){
s++;
map[len+1]=n-i;
//print(len+2);
}
long s1= 0;
Object obj= null;
if( (obj=cache.get(""+(n-i)+","+min))==null)
{
s1= split2AndPrint(n-i,min,len+1);
cache.put(""+(n-i)+","+min,new Long(s1));
}
else
{
s1=((Long)obj).longValue();
System.out.println("hit:"+(n-i)+" "+min);
}
//System.out.println(""+(n-i)+" "+min);
s += s1;
}
return s;
}
