OJ Board

As long as you know the bound (MAX) you can do it in O(n^2) by keeping a table.
int bigarr[MAX];
bigarr[0]=1; /* rest all 0 */
int arr[]={1,3,4,5,9};

for(i=0;i<sizeof(arr);i++)
{
for(j=MAX-1;j>=1;j--)
if(bigarr[j]==1)
{

bigarr[j+arr ]++;
}
}

for(j=0;j<sizeof(arr[];j++)
if(bigarr[arr[j]]!=1 ...