CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

# Thread: Help me understand this algorithm.

1. Senior Member
Join Date
Jul 2005
Posts
1,030

## Help me understand this algorithm.

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,
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.```

2. Member
Join Date
Feb 2013
Posts
58

## Re: Help me understand this algorithm.

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.

3. ## Re: Help me understand this algorithm.

Using the function from previous thread to enumerate subsets, one possible c++ implementation could be
Code:
```#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;
}```
Last edited by 2kaud; November 7th, 2014 at 04:08 PM. Reason: Code change

4. Senior Member
Join Date
Jul 2005
Posts
1,030

## Re: Help me understand this algorithm.

Originally Posted by 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.
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.

5. Member
Join Date
Feb 2013
Posts
58

## Re: Help me understand this algorithm.

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.

6. Member
Join Date
Feb 2013
Posts
58

## Re: Help me understand this algorithm.

huh, something became a bit clear

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

Code:
```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.

7. Member
Join Date
Feb 2013
Posts
58

## Re: Help me understand this algorithm.

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

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•