/* Author: Susam Pal */

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

static unsigned total;
static unsigned matches;

unsigned add(unsigned *count, unsigned *set, unsigned len) {
  unsigned sum = 0;
  unsigned i;
  for (i = 0; i < len; i++)
    sum += count[i] * set[i];
  return sum; 
}

void print(unsigned *set, unsigned *count, unsigned len, unsigned sum) {
  int i;
  for (i = 0; i < len; i++) {
    printf("[%u]*%u %c ", set[i], count[i], i == len - 1 ? '\n' : '+');
  }
}

void decompose(unsigned *set, unsigned len, unsigned target) {
  unsigned *count = (unsigned *) calloc(len, sizeof (unsigned));
  unsigned i, sum, found = 0;
  int matches;

  for (;;) {
    i = 0;
    if ((sum = add(set, count, len)) == target) {
      found++;
      print(set, count, len, sum);
    }
    while (sum > target) {
      count[i] = 0;
      if (++i == len)
        goto end;
      count[i]++;
      if ((sum = add(set, count, len)) == target) {
        found++;
        print(set, count, len, sum);
      }
    }
    count[0]++;
   }
end:
  ;
}

int main(int argc, char **argv) {

  unsigned i;       /* Loop counter */
  unsigned *set;    /* Set of numbers to be used to form the sum */
  unsigned len;     /* Number of integers in the set */
  unsigned target;     /* Target sum */
 
  len = argc - 2;
  set = (unsigned *) calloc(len, sizeof (unsigned));
  target = atoi(argv[argc - 1]);

  /* printf("argv[1] = %s\n", argv[1]);
  printf("argv[1] = %u\n", atoi(argv[1])); */
 
  for (i = 0; i < len; i++)
    set[i] = atoi(argv[i + 1]);

  decompose(set, len, target);

  return 0;
}