递归与分治－－整数划分问题

问题：
一个正整数n可以表示为一系列正整数之和，现在将所有不同的划分打印出来。
书上给出的递归定义如下：
在正整数n的所有不同的划分中，将最大加数n1不大于m的划分个数记作q(n,m)，其递归关系如下：
1：q(n,1) = 1,n>=1
2：q(n,m) = q(n,n), n3：q(n,n) = 1 ＋ q(n,m)
4：q(n,m) = q(n-m,m) + q(n,m-1), n>m
现在我们对其稍作改动，将其组和形式打印出来，程序代码如下：

#include

/* NUM means the given number which is used to be split */
#define NUM 6

/* print the array */
void pfarr( const int arr[], const int len )
{
  int i = 0;
  for (i=0; i    {
      if (arr[i] != 0)
    {
      printf( "%d + ", arr[i] );
    }
     
    }
  printf( "\b\b\b   \n" );    /* erase the last "+" */
}

/* split the given integer */
void IntSplit( int n, int m, int arr[], const int len, int index )
{
  int temp;

  if (n<=0 || m<=0)
    {
      return;
    }
  else if ( 1 == n )
    {
      arr[index] = 1;
      pfarr( arr, len );
      arr[index] = 0;
    }
  else if( 1 == m )
    {
      temp = n;
     
      while (n)
    {
      arr[index] = 1;
      index++;
      n--;
    }
      index--;
      pfarr( arr, len );
      while (n    {
      arr[index] = 0;
      index--;
      n++;
    }
           
    }
  else if( n==m )
    {
      arr[index] = n;
      pfarr(arr, len);
      arr[index] = 0;        /* recover the array */
      IntSplit( n, m-1, arr, len, index );
    }
  else if( n    {
      IntSplit( n, n, arr, len, index );
    }
  else if( n>m )
    {
      arr[index] = m;
      IntSplit( n-m , m, arr, len, index+1 );
      arr[index] = 0;        /* recover the array */

      IntSplit( n, m-1, arr, len, index );
    }
}
 
int main(int argc, char * argv[])
{
  int arr[NUM] = {0} ;
  IntSplit( NUM, NUM, arr, NUM, 0);

  return 0;
 
}

其结果为：
6  
5 + 1  
4 + 2  
4 + 1 + 1  
3 + 3  
3 + 2 + 1  
3 + 1 + 1 + 1  
2 + 2 + 2  
2 + 2 + 1 + 1  
2 + 1 + 1 + 1 + 1  
1 + 1 + 1 + 1 + 1 + 1