Different ways of suming specific numbers to gain 100

Question

I want to write a code to show how many ways one can sum up 5 different numbers to get 100. For example, the numbers are 2,5,10,20,50, and they can be repeated any number of times. Here 50+50 is one way and 20+20+20+20+20. I have no idea how to program this.

I think it should be done by a recursive function, and I've tried to write one without actually knowing how, so this is the best that I came up with:

#include<iostream>
#include<vector>

using namespace std;


int i,sum,n=5,counter=0;


int add(vector<int> &m){

    if(m.size()==0) return 0 ;

    for(i=0 ; i<m.size() ; i++ ){

          sum=m[i]+add(m);
          cout<< sum<<endl;
        if(n>0) n--;
        m.resize(n);
    }


}


int _tmain(int argc, _TCHAR* argv[])
{
    int i,sum,n=5;

vector<int> m;

m.resize(5);

m[0]=2;
m[1]=5;
m[2]=10;
m[3]=20;
m[4]=50;

add(m);


    return 0;
}

Answer 1

Just for fun

#include <iostream>
#include <vector>
#include <iterator>
#include <numeric>
#include <algorithm>

static const int terms[] = { 2,5,10,20,50,   /*end marker*/0 };

using namespace std;
typedef vector  <int> Solution;
typedef vector  <Solution> Solutions;

inline int Sum(const Solution& s)
{
    return accumulate(s.begin(), s.end(), 0);
}

template <typename OutIt>
    OutIt generate(const int target, const int* term, Solution partial, OutIt out)
{
    const int cumulative = Sum(partial); // TODO optimize

    if (cumulative>target)
        return out;         // bail out, target exceeded

    if (cumulative == target)
    {
        (*out++) = partial; // report found solution
        return out;
    } else
    {
        // target not reached yet, try all terms in succession
        for (; *term && cumulative+*term<=target; term++)
        {
            partial.push_back(*term);
            out = generate(target, term, partial, out); // recursively generate till target reached
            partial.pop_back();
        }
        return out;
    }
}

Solutions generate(const int target)
{
    Solutions s;

    generate(target, terms, Solution(), back_inserter(s));

    return s;
}

void Dump(const Solution& solution)
{
    std::copy(solution.begin(), solution.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << std::endl;
}

#ifdef _TCHAR
int _tmain(int argc, _TCHAR* argv[])
#else
int main(int argc, char* argv[])
#endif
{
    Solutions all = generate(100);
    for_each(all.rbegin(), all.rend(), &Dump);
    return 0;
}

$0.02

---

In an effort to actually answer the question, I removed all the unneeded output of solutions, optimizing the code greatly. It is now much more efficient (I benchmarked it at 25x faster with target=2000) but it still doesn't scale to large targets...

#include <iostream>
#include <vector>

using namespace std;

size_t generate(const int target, vector<int> terms)
{
    size_t count = 0;

    if (terms.back()<=target)
    {
        int largest = terms.back();
        terms.pop_back();
        int remain = target % largest;

        if (!remain)
            count += 1;

        if (!terms.empty())
            for (; remain<=target; remain+=largest)
                count += generate(remain, terms);
    }

    return count;
}

int main(int argc, char* argv[])
{
    static const int terms[] = {2,5,10,20,50};
    std::cout << "Found: " << generate(1000, vector<int>(terms, terms+5)) << std::endl;
    return 0;
}

Hopefully the smarter modulo arithmetic begins to reflect what PengOne suggested about approaching this problem.

Answer 2

This problem can be solved theoretically using generating functions. A generating function isn't a function and it doesn't generate anything (good name, eh?), but it does keep track of information very well. The upshot is that the answer to your problem is that the number of ways is equal to the coefficient of x^100 in the expansion of

1/(1-x^2) * 1/(1-x^5) * 1/(1-x^10) * 1/(1-x^20) * 1/(1-x^50) 

Here's the explanation as to why. Recall that 1/(1-x) = 1 + x + x^2 + x^3 + .... This is the basic generating function that we're going to use to solve the problem.

Consider that you have numbers A,B,...,N (in your example, they are 2,5,10,20,50) that you can repeat any number of times. Then consider the (generating) function

f(x) = 1/(1-x^A) * 1/(1-x^B) * ... * 1/(1-x^N)

The coefficient of x^M in f(x) is the number of ways to write M as a sum of the form

M = a*A + b*B + ... + n*N

where a,b,...,n are nonnegative integers.

Why does this work? Because any monomial term in the expansion f(x) comes from taking one term from 1/(1-x^A) which will look like x^(a*A) for some nonnegative a, and similarly for the other terms. Since the exponents add, the coefficient of x^M is all the ways of writing such a sum to get M.

I know this isn't a programming answer, but hopefully you can use the idea to write a program.

Answer 3

The code you have at the moment for the function add will get you a stack overflow :) Because you do the recursive call to add(m) before modifying the vector m. So add gets called always with an unmodified vector and the base case never gets hit.

I don't know if I catched what you want to do, but what about:

#include <iostream>
#include <sstream>
#include <vector>

void add(int i, std::string s, int sum)
{
    if (sum == 100)
    {
      std::cout << s << "=100" << std::endl;
      return;
    }
    if (sum > 100)
    {
       return;
    }
    if (sum < 100)
    {
      std::ostringstream oss;
      oss << s << "+" << i;
      add(i, oss.str(), sum+i);
    }
}

int main()
{
  std::vector<int> m;

  m.resize(5);

  m[0]=2;
  m[1]=5;
  m[2]=10;
  m[3]=20;
  m[4]=50;

  // This loop will initiate m.size lines of recursive calls
  // one for each element of the array
  for (size_t i = 0; i < m.size(); i++)
  {
    add(m[i], "", 0);
  }

  return 0;
}

Answer 4

Here is a recursive solution: http://ideone.com/ip98M

#include <iostream>

template<size_t N>
void find_combinations_helper(int total, const int (&denoms)[N], int denoms_used, int remaining, int (&counts)[N])
{
    if (remaining == 0) {
        int partial_sum = 0;
        for( int i = 0; i < denoms_used; ++i ) {
           if (counts[i]) {
               std::cout << counts[i] << "*" << denoms[i];
               partial_sum += counts[i] * denoms[i];
               if (partial_sum < total) std::cout << " + ";
           }
        }
        std::cout << "\n";
        return;
    }

    if (denoms_used == N) return;

    for( counts[denoms_used] = 0; remaining >= 0; (remaining -= denoms[denoms_used]), ++counts[denoms_used] )
        find_combinations_helper(total, denoms, denoms_used + 1, remaining, counts);
}

template<size_t N>
void find_combinations( int total, const int (&denoms)[N] )
{
    int solutions[N];
    find_combinations_helper(total, denoms, 0, total, solutions);
}

int main(void) {
    const int bill_denoms[] = { 50, 20, 10, 5, 2 };
    find_combinations(100, bill_denoms);
}

Answer 5

This doesn't look right:

m[0]=2;
...
m[0]=50;

Shoudn't that be m[4]=50;?

Edit You never declare the value 100 how do you know when you reached 100?