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

void exchangeRec ( int n, int c, int d, int *A, int i, int sum )
{
   int j;

   if (sum > n) return;

   if (sum == n) {
      printf("    ");
      for (j=0; j<i; ++j) printf("%d%c", A[j], (j == i-1) ? '\n' : '+');
   }

   A[i] = c; exchangeRec(n,c,d,A,i+1,sum+c);
   A[i] = d; exchangeRec(n,c,d,A,i+1,sum+d);
}

void exchangeItr ( int c, int d, int n )
{
   int maxcnt, sum;
   unsigned int i, j, t;

   maxcnt = (c >= d) ? n / d : n / c;
   if (maxcnt > 31) {
      printf("!!! Sorry, the iterative method will not work...\n");
      return;
   }
   for (i=0; i<=(1U<<maxcnt); ++i) {
      t = i; sum = n;
      for (j=0; (j<=maxcnt) && (sum > 0); ++j) {
         sum -= (t & 1U) ? c : d;
         t >>= 1;
      }
      if ((sum == 0) && (t == 0)) {
         t = i; sum = n;
         printf("    ");
         while (1) {
            if (t & 1U) {
               printf("%d", c);
               sum -= c;
            } else {
               printf("%d", d);
               sum -= d;
            }
            if (sum == 0) {
               printf("\n");
               break;
            }
            printf("+");
            t >>= 1;
         }
      }
   }
}

int main ()
{
   int c, d, n;
   int *A;

   do { printf("c = "); scanf("%d", &c); } while (c <= 0);
   do { printf("d = "); scanf("%d", &d); } while ((d <= 0) || (d == c));
   do { printf("n = "); scanf("%d", &n); } while (n <= 0);

   printf("\n+++ Recursive method\n");
   A = (int *)malloc(n * sizeof(int));
   exchangeRec(n,c,d,A,0,0);
   free(A);

   printf("\n+++ Iterative method\n");
   exchangeItr(c,d,n);

   exit(0);
}