子集和数问题的实现

源代码：

#include <stdio.h>
#define N 8
int X[N]={0};
int W[N];
int M,NUM=0;
int main()
{
 void input();
 void sumofsub(int,int,int);
 int s,r,k;
 input();
 s = r = 0;
 for(k=0;k<N;k++)
  r += W[k];
 k = 0;
 if(M > r || M < W[0])
  printf("no answer!\n");
 else
 {
  sumofsub(s,k,r);
 }
 return 0;
}
void input()
{
 int i;
 printf("input the set of W[1-%d]:",N);
 for(i=0;i<N;i++)
 {
  scanf("%d",&W[i]);
 }
 printf("input the sum M = ");
 scanf("%d",&M);
}
void sumofsub(int s,int k,int r)
{
 void print(int);
 X[k] = 1;
 if(s+W[k] == M)
  print(k);
 else
 {
  if(s+W[k]+W[k+1] <= M)
   sumofsub(s+W[k],k+1,r-W[k]);
 }
 if(s+r-W[k] >= M && s+W[k+1] <= M)
 {
  X[k] = 0;
  sumofsub(s,k+1,r-W[k]);
 }
}
void print(int k)
{
 int i;
 NUM++;
 printf("the %dth answer is:",NUM);
 for(i=0;i<=k;i++)
 {
  printf("%d ",X[i]);
 }
 for(;i<N;i++)
 {
  printf("%d ",0);
 }
 printf("\n");
}

结果：

input the set of W[1-8]:1 2 3 4 5 6 7 8
input the sum M = 8
the 1th answer is:1 1 0 0 1 0 0 0
the 2th answer is:1 0 1 1 0 0 0 0
the 3th answer is:1 0 0 0 0 0 1 0
the 4th answer is:0 1 0 0 0 1 0 0
the 5th answer is:0 0 1 0 1 0 0 0
the 6th answer is:0 0 0 0 0 0 0 1