
November 6th, 2014, 08:36 PM
#1
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=suma[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.

November 7th, 2014, 02:31 PM
#2
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 wellwritten. 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.

November 7th, 2014, 03:38 PM
#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
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only  not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums  and not via private messages!
C++17 Compiler: Microsoft VS2019 (16.7.3)

November 10th, 2014, 01:32 PM
#4
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 wellwritten. 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.

November 10th, 2014, 03:22 PM
#5
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.

November 10th, 2014, 03:54 PM
#6
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.

November 10th, 2014, 04:23 PM
#7
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

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
