CareerCup

int sumCount(int* arr, int len, int total)
{
    int count = 0;
    for (int i = 0; i < len; ++i)
    {
        sumCountHelper(arr, i, len, total - arr[i], count);
    }
    return count;
}

void sumCountHelper(int* arr, int start, int len, int total, int& count)
{
    if (total == 0)
    {
        ++count;
        return;
    }
    if (total < 0)
        return;
   for (int i = start + 1; i < len; ++i)
    {
        sumCountHelper(arr, i, len, total - arr[i], count) ;
    }
}

Apply the subset algorithm -- iterate from 1 to (2^(array size) - 1). Use binary representation of i to select numbers that have 1 at corresponding position. Get sum of it. If it's equals to sought, output/count.

Mr Nasser Ghazali.
plz explain your solution .. am not able to trace it..

def sum_count(alist, target):
	if len(alist) == 0 or target < 0:
		return 0
	elif alist[0] == target:
		return sum_count(alist[1:], target) + 1
	else:
		return sum_count(alist[1:], target) + sum_count(alist[1:], target - alist[0])

int sumcount(int *arr,int len,int total)
{
int count=0,i,j;
int tot;
for(i=0;i<len;i++)
{
tot=total-arr[i];
for(j=i+1;j<len;j++)
{

tot=tot-arr[j];
if(tot==0)
{
count++;
tot=tot+arr[j];
}
if(tot<0)
break;
}
}
return count;
}

int A[]={10, 5, 2, 3 , 7, 8};
int X=15;
int findSum(int idx, int sum, int totalMatches)
{
	int n=sizeof(A)/sizeof(int);
	if(idx==n)
		return totalMatches;
	if(sum+A[idx]>X)
		return findSum(idx+1, sum, totalMatches);
	else if(sum+A[idx]==X)
		return totalMatches+1;
	else
	{
		int tot=0;
		for(int j=idx+1; j<n; j++)
			 tot+=findSum(j, sum+A[idx], 0);
		return totalMatches+tot;
	}
}

and for computing the total subsets call the above function as :

int tot = 0;
	for(int i=0; i<sizeof(A)/sizeof(int); i++)
		tot+=findSum(i, 0, 0);