Partitioning a no. N into M partitions
I'm trying a problem in which I have to partition a no. N into M partitions as many as possible.

Example:

N=1 M=3 , break 1 into 3 parts

0 0 1   
0 1 0   
1 0 0

N=3 M=2 , break 3 into 2 parts

2 1   
1 2   
3 0   
0 3   

N=4 M=4 , break 4 into 4 parts

0 0 0 4   
0 0 4 0   
0 4 0 0   
4 0 0 0   
0 0 1 3   
0 1 0 3   
0 1 3 0   
.     
.      
.

and so on.

I did code a backtrack algo. but for it but it chokes for some larger input.Can anybody help in providing a more efficient method.

My method:


    void backt(int* part,int pos,int n) //break N into M parts
    {
        if(pos==M-1)
        {
            part[pos]=n;
            ppart(part);   //print part array
            return;
        }

        if(n==0)
        {
            part[pos]=0;
            backt(part,pos+1,0);
            return;
        }

        for(int i=0;i<=n;i++)
        {
            part[pos]=i;

            backt(part,pos+1,n-i);
        }
    }



In my algo. n is N and it fill the array part[] for every possible partition of N.

Thanks


Partitioning a no. N into M partitions
===

I'm trying a problem in which I have to partition a no. N into M partitions as many as possible.

Example:

N=1 M=3 , break 1 into 3 parts

0 0 1   
0 1 0   
1 0 0

N=3 M=2 , break 3 into 2 parts

2 1   
1 2   
3 0   
0 3   

N=4 M=4 , break 4 into 4 parts

0 0 0 4   
0 0 4 0   
0 4 0 0   
4 0 0 0   
0 0 1 3   
0 1 0 3   
0 1 3 0   
.     
.      
.

and so on.

I did code a backtrack algo. but for it but it chokes for some larger input.Can anybody help in providing a more efficient method.

My method:


    void backt(int* part,int pos,int n) //break N into M parts
    {
        if(pos==M-1)
        {
            part[pos]=n;
            ppart(part);   //print part array
            return;
        }

        if(n==0)
        {
            part[pos]=0;
            backt(part,pos+1,0);
            return;
        }

        for(int i=0;i<=n;i++)
        {
            part[pos]=i;

            backt(part,pos+1,n-i);
        }
    }



In my algo. n is N and it fill the array part[] for every possible partition of N.

Thanks

