Saturday 14 September 2013

subset sum problem

#include<stdio.h>

int memo[6][10];

int subset_sum(int *a,int sum,int n)
{
                   if(sum==0)
                   {        
                             return 1;
                   }
                   if(n==0 && sum!=0)
                   {
                           return 0;
                   }
                   if(a[n-1]>sum)
                                   return subset_sum(a,sum,n-1);
                 
                   if(memo[n][sum]!=0) return memo[n][sum];
                   else
                   return memo[n][sum]= subset_sum(a,sum-a[n-1],n-1) || subset_sum(a,sum,n-1);                    
}
main()
{
      int a[]={3,34,4,12,5,2,5,6};
      int sum=35;
      int i=0;
      int j=0;
      for(;i<6;i++)
      {
              for(;j<20;j++)
              {
                      memo[i][j]=0;
              }
      }
      printf("%d\n\n",subset_sum(a,sum,6));
      getch();
}

No comments:

Post a Comment

Have some problem with this code? or Request the code you want if you cant find it in Blog Archive.