2012年Google校园招聘笔试最后一题

给定一个正整数N（N<1000000），输出用1，5，10，20，50，100组合出N的总共组合方式。

用C++递归实现如下：

#include<iostream>
using namespace std;
int num;
void countCombinationNum(int a[], int len, int base, int N)
{
if (N==0)
{
num++;
return;
}else if (N<0)
{
return;
}else
{
for (int i=base;i<len;i++)
{
countCombinationNum(a, len, i, N-a[i]);
}
}
}
int main()
{
int a[] = {1,5,10,20,50,100};
int N = 500;
countCombinationNum(a, sizeof(a)/sizeof(int), 0, N);
cout<<num<<endl;
return 0;
}