// Subset sums by dynamic programming.  Determines if there
// is a subset of a multiset (bag) of numbers such
// that adds to a target value.
//

#include <stdio.h>

int *inSet;   // Input set of numbers, inSet[0] is not used
short *tab;   // tab[i] gives the smallest value k such that
              // some subset of {inSet[1] . . . inSet[k]}
              // has a sum of i.  Initialized to UNTOUCHED
              // and will be set to IMPOSSIBLE if no such k
              // exists.
              // BEFORE READING THE REST OF THE CODE, appreciate
              // the following result (DP lemma):
              //
              // If tab[i]=k such that k is the smallest
              // value such that some subset of {inSet[1] . . . inSet[k]},
              // has a sum of i, then inSet[k] must be included in the
              // sum.

char *inSubset; // inSubset[i]=TRUE iff inSet[i] is assigned
                // to first set when tracing back from
                // dynamic programming.
int sum,target,ksum; // Sum of input values, target value, sum
                     // of first k values
int setSize;         // Number of input values
int i,j,k;

#define FALSE 0
#define TRUE 1

#define UNTOUCHED 15000
#define IMPOSSIBLE 16000

// setMin is used to update tab[sum] with a smaller value for choosing
// the subset from.
#define setMin(sum,index) (tab[sum]=(tab[sum]>index) ? index:tab[sum])

void shellsort(a,N)
int *a;
int N;
{
int group;
int i,j,h;
int v;
for (h=1;h<=N/9; h=3*h+1) ;
for (;h>0; h /= 3)
  for (group=0; group<h; group++)
    for (i=group+h; i<N; i+=h)
    {
      v=a[i];
      j=i;
      while (j>=h && a[j-h]>v)
      {
        a[j]=a[j-h];
        j -= h;
      }
      a[j]=v;
    }
}

main()
{
sum=0;
printf("Enter size of set\n");
scanf("%d",&setSize);

inSet=(int*) malloc((setSize+1)*sizeof(int));
inSubset=(char*) malloc(setSize+1);
if (!inSet || !inSubset)
{
  printf("malloc failed\n");
  exit(0);
}

printf("Enter numbers, one per line\n");
for (i=1;i<=setSize;i++)
{
  scanf("%d",&inSet[i]);
  inSubset[i]=FALSE;
  sum += inSet[i];
}

printf("Enter target value\n");
scanf("%d",&target);

shellsort(&inSet[1],setSize);

// Note: the size of tab can easily be exponential based on setSize.
tab=(short*) malloc((target+1)*sizeof(short));
if (!tab)
{
  printf("EXITING - malloc(failed)!!!\n");
  exit(0);
}

for (i=0;i<=target;i++)
  tab[i]=UNTOUCHED; // indicates that subset sum to equal i has not been found
                    // yet
for (i=1;i<=setSize;i++) // Record singleton subsets
  setMin(inSet[i],i);

ksum=0;
k=0;
for (i=1;i<=target;i++) // each i iteration sets tab[i] to its final value
{
  // updates k and ksum so that minimum feasible value of tab[i] is known
  while (ksum<i)
  {
    k++;
    ksum+=inSet[k];
  }

  for (j=k;j<=setSize;j++)
    if (inSet[j]>=i) // this is why the input values were sorted -
      break;         // there is no point in continuing loop,
                     // since remaining input values are too big.
    else if (tab[i-inSet[j]]!=IMPOSSIBLE && j>tab[i-inSet[j]])
    // have tab[i]'s value based on DP lemma
    {
      setMin(i,j);
      break;
    }
  if (tab[i]==UNTOUCHED) // Record permanent failure
    tab[i]=IMPOSSIBLE;
}

if (target<=50)
{
  printf(" i   inSet[i]\n");
  printf("--- ----------\n");
  for (i=1;i<=setSize;i++)
    printf("%3d     %4d\n",i,inSet[i]);
  printf(" i   tab[i]\n");
  printf("--- --------\n");
  for (i=1;i<=target;i++)
  {
    printf("%3d ",i);
    if (tab[i]==IMPOSSIBLE)
      printf("IMPOSSIBLE\n");
    else
      printf("%5d (%d)\n",tab[i],inSet[tab[i]]);
  }
}

if (tab[target]==IMPOSSIBLE)
  printf("no solution\n");
else
{
  // traceback based on DP lemma to get subset
  sum=target;
  while (inSet[tab[sum]]!=sum)
  {
    inSubset[tab[sum]]=TRUE;
    sum-=inSet[tab[sum]];
  }
  inSubset[tab[sum]]=TRUE;
  printf("Subset\n");
  for (i=1;i<=setSize;i++)
    if (inSubset[i])
      printf("%d\n",inSet[i]);
}
free(tab);
free(inSet);
free(inSubset);
}