N Integers – Sum S – All Combinations(Weekly Test)

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

 Code:

#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;

}