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

/* For i=0,1,2,...,k-1, B[i] stores the first index from which i+1 starts
 * in A[]. The array A[] itself is neither created nor maintained.
 * Initially, B[0] = 0 to indicate that 1 starts from index 0 in A[].
 * Also, we set B[k] = n for printing convenience to indicate that k+1
 * starts at index n in A[].
 *
 * n, k are the integers supplied by the user.
 *
 * t is the current integer for which the starting index in A[] is to be
 * determined.
 */
int genidxarr ( int *B, int n, int k, int t )
{
   int i, j, cnt = 0;

   /* If the starting indices are fixed for 1,2,...,k, we have detected
    * one valid arrangement. Print it and return 1.
    */
   if (t == k+1) {
      for (i=1; i<=k; ++i) {
         /* Print the requisite number of i's. Note that in A[], i starts
          * from index B[i-1], and i+1 starts from index B[i].
          */
         for (j=B[i-1]; j<B[i]; ++j) printf("%d ",i);
      }
      printf("\n");
      return 1;
   }

   /* Determine all possibilities from which t may start in A[].
    * t-1 starts in A[] from index B[t-2], so the smallest index from
    * which t may start is B[t-2]+1. The largest starting index for t
    * is trivially n-1. However, we can make it more conservative.
    * After t is placed, there are k-t integers remaining to be placed
    * in A[], each of which must appear at least once. Therefore, we
    * need to leave at least k-t cells, that is, the achievable upper
    * bound on the starting index of t is (n-1)-(k-t). The program
    * works perfectly even when n-1 is used as the upper bound, but
    * that leads to many unsuccessful recursive calls returning zero.
    */
   for (i=B[t-2]+1; i<=n-k+t-1; ++i) {
      B[t-1] = i;                  /* Set the starting index for t */
      cnt += genidxarr(B,n,k,t+1); /* Recursively place t+1 through k */
   }

   return cnt;
}

int main ()
{
   int k, n, *B, cnt;

   printf("n = "); scanf("%d", &n);
   printf("k = "); scanf("%d", &k);

   if ((n <= 0) || (k <= 0)) {
      fprintf(stderr, "Enter positive integers as n and k.\n");
      exit(1);
   }

   /* Only the index array is used. A[] is not explicitly used. */
   B = (int *)malloc((k+1) * sizeof(int));

   /* 1 starts from index 0 in A[]. For convenience, we also set B[k] = n. */
   B[0] = 0; B[k] = n;

   /* Recursively decide the starting indices in A[] of 2 through k */
   cnt = genidxarr(B,n,k,2);
   printf("Total number of possibilities is %d\n", cnt);

   free(B);
   exit(0);
}