CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Help me understand this algorithm.

  1. #1
    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. #2
    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. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,257

    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)

  4. #4
    Join Date
    Jul 2005
    Posts
    1,030

    Re: Help me understand this algorithm.

    Quote Originally Posted by S@rK0Y View Post
    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. #5
    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. #6
    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. #7
    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
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)