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

int populateArray ( int A[] )
{
   int n, i;

   printf("Enter array size (between 1 and 20): ");
   scanf("%d", &n);
   if ((n <= 0) || (n > 20)) n = 10;
   for (i=0; i<n; ++i) {
      A[i] = 1 + rand() % 10;
      printf("A[%d] = %2d\n", i, A[i]);
   }
   return n;
}

void sumCheck ( int A[], int n, int sum )
{
   unsigned int i, c;
   int s;

   if (sum == 0) {
      printf("   0\n");
      return;
   }
   for (c = 0; c < (1U << n); ++c) {
      s = 0;
      for (i = 0; i < n; ++i) if (c & (1U << i)) s += A[i];
      if (s == sum) {
         printf("%4d = ", sum);
         s = 0; i = 0;
         while (1) {
            if (c & (1U << i)) {
               s += A[i];
               printf("A[%d]", i);
               if (s == sum) break;
               printf(" + ");
            }
            ++i;
         }
         printf(" = ");
         s = 0; i = 0;
         while (1) {
            if (c & (1U << i)) {
               s += A[i];
               printf("%d", A[i]);
               if (s == sum) break;
               printf(" + ");
            }
            ++i;
         }
         printf("\n");
         return;
      }
   }
   printf("The sum %d cannot be realized using the array\n", sum);
}

void helper ( int A[], int n, int i, int B[], int s, int c )
{
   if (B[s] == -1) B[s] = c;
   if (i == n) return;
   helper(A,n,i+1,B,s+A[i],c+(1U<<i));
   helper(A,n,i+1,B,s,c);
}

void allSumCount ( int A[], int n )
{
   int *B, sum, i, j;
   unsigned int cnt;

   sum = 0; for (i = 0; i < n; ++i) sum += A[i];
   B = (int *)malloc((sum + 1) * sizeof(int));
   for (i = 0; i <= sum; ++i) B[i] = -1;
   helper(A,n,0,B,0,0);
   cnt = 0; for (i = 0; i <= sum; ++i) if (B[i] >= 0) ++cnt;
   printf("%u different sums are possible:\n", cnt);
   printf("   0\n");
   for (i = 1; i <= sum; ++i) if (B[i] >= 0) {
      printf("%4d = ", i);
      cnt = B[i]; j = 0;
      while (1) {
         if (cnt & (1U << j)) {
            printf("A[%d]", j);
            cnt -= (1U << j);
            if (cnt == 0) break;
            printf(" + ");
         }
         ++j;
      }
      printf(" = ");
      cnt = B[i]; j = 0;
      while (1) {
         if (cnt & (1U << j)) {
            printf("%d", A[j]);
            cnt -= (1U << j);
            if (cnt == 0) break;
            printf(" + ");
         }
         ++j;
      }
      printf("\n");
   }
   free(B);
}

int main ()
{
   int n, A[20], sum;

   srand((unsigned int)time(NULL));
   n = populateArray(A);
   printf("Enter sum: "); scanf("%d", &sum);
   sumCheck(A,n,sum);
   allSumCount(A,n);
   exit(0);
}