N Integers – Sum S – All Combinations

 

#include<stdio.h>
#include<string.h>
short int subset[999][999],cnt=0;
void print(int a[],int i,int sum)
{              
        if(sum==0 && i==0)
        {
                cnt++;
                return;
        }
        if(sum!=0 && i==0 && subset[0][sum])
       {
                cnt++;
                return;
        }
        if(subset[i-1][sum]){
                print(a,i-1,sum);
        }
        if(sum>=a[i] && subset[i-1][sum-a[i]]){
                print(a,i-1,sum-a[i]);
        }
}
void build_table(int a[],int n,int sum){
        int i,j;
        memset(&subset,0,sizeof(n*(sum+1)));
        for(i=0;i<n;i++){
                subset[i][0]=1;
        }
      
        if(a[0]<=sum)
                subset[0][a[0]]=1;
        for(i=1;i<n;i++){
                for(j=0;j<sum+1;j++){
                                subset[i][j]=subset[i-1][j]||subset[i-1][j-a[i]];
                }
        }
        print(a,n-1,sum);
}
int main(){
       
        long int sum;
        int n,i;
        scanf(“%ld”,&sum);
        scanf(“%d”,&n);
        int a[n];
        for(i=0;i<n;i++)
                scanf(“%d”,&a[i]);
        build_table(a,n,sum);
        printf(“%d”,cnt);
        return 0;
}