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

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.