正整数N等于M个不同的正整数之和

题目：

正整数N是M个正整数之和，M比N小，且不重复。例如，N=20，M=5，N可以表示成为 
  
1+2+3+4+10 = 20 
1+2+3+5+9 = 20 
1+2+3+6+8 = 20 
1+2+4+5+8 = 20 
1+2+4+6+7 = 20 
1+3+4+5+7 = 20 
2+3+4+5+6 = 20 
Total:7

 

思路：

先确定第一个数是a，然后找出M-1个数的和为N-a

 

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int data[100];
int num = 0;

void output(int total)
{
     for(int i = total;i > 0; i--)
     {
      printf("%d ", data[i]);
     }
     printf("\n");
     num++;
}
void findComb(int total, int count, int sum, int begin)
{
    if( count < 0 )
    {
        printf("error\n");
        return;
    }
    else if( count == 1 )
    {
         data[count] = sum;
         output(total);
         return;
    }
    else
    {
        for(int i = begin; i <= (sum-1)/count; ++i )
        {
             
                data[count] = i;
                findComb(total, count-1, sum-i, i+1);  
        }
    }
}

int main()
{   
 
  findComb(5, 5, 20, 1);
  printf("Total: %d\n", num);
   system("PAUSE");
   return 0;
}