Help me understand this algorithm.

[LarryChen]

Write a function that takes an array of integers and returns the number of combinations of those integers that sum to a certain number. Here is the code,

int FindCount(int a[], int size, int sum)
{
	int i,j;
	int ret = 0;

	int* b = new int[sum+1];

	for(i=1;i<=sum;i++)
		b[i]=0;

	for(i=0;i<size;i++)
	{
		for(j=sum-a[i];j>0;j--)
		{
			if(b[j])
				b[j+a[i]]+=b[j]; //occurence of variety of addition not bigger than sum
		}
		b[a[i]]+=1;
	}

	ret = b[sum];

	delete[] b;

	return ret;
}
I found it pretty tough to master it. What is the idea behind the code? Thanks.

[S@rK0Y]

have you been running that code step by step??? Actually, 'tis the best approach to figure out how stuff works. Meanwhile, i suspect aforementioned algo ain't well-written. Just recall that your thread about method to enumerate subsets. in fact, you must:

1. generate subsets of given array.
2. calculate sum of each subset & try that sum against given number.
3. return the matched results to user.

[2kaud]

Using the function from previous thread to enumerate subsets, one possible c++ implementation could be

#include <iostream>
using namespace std;

int FindCount(int a[], int size, int sum)
{
const int num = 1 << size;
int cnt = 0;

	for (int i = 0, total = 0; i < num; ++i, total = 0)
	{
		for (int j = 0, k = 1; j < size; ++j, k <<= 1)
			if (k & i)
				total += a[j];

		if (total == sum)
			++cnt;
	}
	
	return cnt;
}


int main()
{
const int arrsize = 4;

int a[arrsize];

	for (int i = 0; i < arrsize; ++i)
		a[i] = i + 1;

int sum;

	cout << "Enter sum to find: ";
	cin >> sum;

	cout << "Number of ways to find a total of " << sum << " is " << FindCount(a, arrsize, sum) << endl;
}

[LarryChen]

have you been running that code step by step??? Actually, 'tis the best approach to figure out how stuff works. Meanwhile, i suspect aforementioned algo ain't well-written. Just recall that your thread about method to enumerate subsets. in fact, you must:

1. generate subsets of given array.
2. calculate sum of each subset & try that sum against given number.
3. return the matched results to user.

The algorithm you suggested is pretty straightforward but the time complexity would be n*2^n. The original algorithm I posted is n*sum which is faster. Any idea how the original algorithm works? Thanks.

[S@rK0Y]

Larry, that algo is the really working? i didn't try it, frankly. But such speed seems very intriguing. well, i'll dig in & ans as soon as possible.

[S@rK0Y]

huh, something became a bit clear

Array "b" is used to count how many subsets of array "a" give the needful number:

if(b[j])
				b[j+a[i]]+=b[j]; //occurence of variety of addition not bigger than sum

look at that: found sum is expressed as index of "b". in other words, b[i] stores the number of subsets, which gives sum == i. Quite curious, but (for large sums) completely useless.

[S@rK0Y]

by the way, algo is faulty: it has to control a[i] < sum + 1, otherwise gets a jump to nowhere.