#include <cstdlib>
#include <iostream>

using namespace std;

int main(int argc, char *argv[])
{   
    //Задано n произвольных натуральных чисел
    //Найти все суммы по k чисел, сумма которых равна заданному числу m
    int n; //количество заданных чисел
    int max; //максимальное натуральное число из множества 1..max
    int m; //заданное натуральное число m
    int k;//количество слагаемых в сумме
    int c; //количество сочетаний из n элементов по k элементов (всего сумм)
    int z;//количество сумм, равных заданному числу m
    int s;//сумма
    int i, p, r; 
    printf("input maximum natural number:  max=");
    scanf("%d",&max);
    printf("input quantity of natural numbers:  n = ");
    scanf("%d",&n);
    k=0;
    while ((k<1) || (k>n))
    {
        printf("input quantity of items in sums 0 <= k <= %d :  k = ",n);
        scanf("%d",&k);
    }
    m=0;    
    while ((m<k) || (m>max*k))
    {
        printf("input natural number %d <=  m <= %d  :   m = ", k, max*k);
        scanf("%d",&m);
    }    
    int *x;  //массив из n случайных чисел
    x=new int[n+1];
    srand(time(NULL));
    x[0]=0;
    for (i=1; i<=n; i++) x[i]=rand()%max+1;
    for (i=1; i<=n; i++) printf("x[%2d]=%2d\n",i,x[i]);
    FILE *f;
    f=fopen("comb.txt","w");
    fprintf(f,"Из множества натуральных чисел от 1 до %d\n",max);
    fprintf(f,"выбрано случайно  %d  чисел\n",n);
    fprintf(f,"Список случайных чисел:\n",n); 
    for (i=1; i<=n; i++) fprintf(f,"x[%2d] = %2d\n",i,x[i]);
    fprintf(f,"Заданное натуральное число m = %2d\n",m);
    fprintf(f,"Заданное число слагаемых в сумме k = %2d\n",k);
    fprintf(f,"Суммы из %d слагаемых, равные заданному числу %d\n",k, m);
    int *a;    //массив из индексов 1..k
    a=new int[k+1];
    for (i=0; i<=k; i++)    a[i]=i;   
    p=0;  r=0;  z=0;  c=0;
    while (p<=k-1)
    {
       s=0;    
       for (i=1; i<=k; i++) s=s+x[a[i]];
       c++;
       if (s==m) 
       {
           for (i=1; i<k; i++) printf("x[%2d] + ",a[i]);
           printf("x[%2d] = %d\n",a[k],m); 
           for (i=1; i<k; i++) fprintf(f,"x[%2d] + ",a[i]);
           fprintf(f,"x[%2d] = %d\n",a[k],m);      
           z++;
       }
       while (a[k-p]==n-p) p++;
       a[k-p]++;
       for (r=0; r<p; r++) a[k-p+r+1]=a[k-p+r]+1; 
       if (p<=k-1) p=0; 
    }
    printf("Total quantity of sums : %d sums\n",c);
    printf("%d sums equal %d\n",z, m); 
    fprintf(f,"Из %d сумм %d сумм равны %d\n",c,z,m);
    fclose(f);
    printf("look the file 'comb.txt' \n"); 
    system("PAUSE");
    return EXIT_SUCCESS;
}