subset sum count

# problem statement

N Integers - Sum S - All Combinations

A number S is passed as input. Also N positive unique integers are passed as input to the program. One or more numbers (out of these N integers) can be added to form the number S. Several such combinations are possible and the program must print the count C of such combinations.
You need to optimize the code so that it executes within the given time (failing which Time exceeded Error will be obtained).

Input Format:
The first line will contain S and N separated by a space.
The second line will contain the value of N positive integers, with the values separated by a space.

Output Format:
The first line will contain the the count C

Boundary Conditions:
1 <= S <= 99999
2 <= N <= 50

Example Input/Output 1:
Input:
10 5
1 2 3 4 5

Output:
3

Explanation:
The three combinations which add up to 10 are
1 4 5
2 3 5
1 2 3 4

Example Input/Output 2:
Input:
140 20
73 50 90 41 81 31 7 16 27 95 58 72 92 3 30 13 2 36 68 59

Output:
98

Explanation:
The 98 combinations that add up to 140 are
50 90
81 59
72 68
73 31 36
50 31 59
41 31 68
41 7 92
41 27 72
13 68 59
73 7 58 2
50 41 13 36
50 81 7 2
50 16 72 2
50 58 30 2
90 41 7 2
90 31 16 3
90 7 16 27
90 7 30 13
41 81 16 2
41 27 13 59
81 7 16 36
81 16 30 13
81 27 30 2
31 7 72 30
7 16 58 59
7 95 2 36
7 58 72 3
7 72 2 59
16 27 95 2
16 58 30 36
16 92 30 2
95 30 13 2
72 30 2 36
73 41 7 16 3
73 31 7 16 13
73 31 7 27 2
73 7 27 3 30
73 16 13 2 36
50 41 31 16 2
50 41 16 3 30
50 31 7 16 36
50 31 16 30 13
50 31 27 30 2
50 7 13 2 68
50 16 58 3 13
50 16 13 2 59
50 27 58 3 2
50 72 3 13 2
90 7 27 3 13
41 81 3 13 2
41 31 7 58 3
41 31 7 2 59
41 31 30 2 36
41 7 3 30 59
41 16 13 2 68
41 58 3 2 36
81 7 3 13 36
81 16 27 3 13
31 7 16 27 59
31 7 27 72 3
31 7 30 13 59
31 16 27 30 36
31 58 13 2 36
31 3 2 36 68
7 16 13 36 68
7 27 2 36 68
7 58 3 13 59
7 92 3 2 36
16 27 58 3 36
16 27 92 3 2
16 27 2 36 59
16 72 3 13 36
27 95 3 13 2
27 72 3 2 36
27 30 13 2 68
58 3 30 13 36
92 3 30 13 2
30 13 2 36 59
50 41 31 3 13 2
50 41 7 27 13 2
50 31 7 3 13 36
50 31 16 27 3 13
41 31 16 3 13 36
41 31 27 3 2 36
41 7 16 27 13 36
81 31 7 16 3 2
31 7 27 3 13 59
31 16 58 3 30 2
31 27 3 30 13 36
7 16 27 58 30 2
7 16 72 30 13 2
27 3 13 2 36 59
41 31 7 16 30 13 2
41 7 16 58 3 13 2
31 7 16 3 13 2 68
7 16 27 72 3 13 2
7 27 58 3 30 13 2
41 31 7 16 27 3 13 2


This is based on subset sum and it can be solve it efficieently using "Dynamic programming strategy" 
My solution

#include<stdio.h>
#include<string.h>
short int subset[999][999],cnt=0;
void print_subset_count(int a[],int i,int sum){                 // this funtion count the number of subset present
        if(sum==0 && i==0){
                cnt++;
                return;
        }
        if(sum!=0 && i==0 && subset[0][sum]){
                cnt++;
                return;
        }
        if(subset[i-1][sum]){
                print_subset_count(a,i-1,sum);
        }
        if(sum>=a[i] && subset[i-1][sum-a[i]]){
                print_subset_count(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;
        }
        //check if a[0] is less than sum then set true for the choice
        if(a[0]<=sum)
                subset[0][a[0]]=1;
        /*
         * fill the table using the formula
         *
         * current =  above value (i-1)(j) (or) value (i-1)(j-a[i])
         *
         * value(i-1)(j-a[i]) if the sum can be formed using 0..j subset
         *
         * */
        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 the subset table
        for(i=0;i<n;i++){
                for(j=0;j<sum+1;j++){
                        printf("%d ",subset[i][j]);
                }
                printf("\n");
        }
        //important check whether the subset is present or not
        if(subset[n-1][sum]==0){
                printf("there are no subsets %d %d",n-1,sum);
                return;
        }
        //cool we completed table then we need to find the subset
        //this is done using recursion procedure
        //traversing from subset[i-1][sum]
        // two ways we can get subset
        // a) including elements eg: sum=10 list=1,2,3 include 4
        // b) excluding elements eg: sum=10 list=1,2,4,5 exclude 2
        // let's do it
        print_subset_count(a,n-1,sum);
}
int main(){
        //int a[]={73,50,90,41,81,31,7,16,27,95,58,72,92,3,30,13,2,36,68,59};
        //int n=20,sum=140;
        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;
}


Resources:
https://www.youtube.com/watch?v=zKwwjAkaXLI   					                    // Video about subset problems
http://www.geeksforgeeks.org/perfect-sum-problem-print-subsets-given-sum/	  //full program procedure

i changed the above program to work for this problem suitation