每日一题C++版（拼凑面额）

编程是很多偏计算机、人工智能领域必须掌握的一项技能，此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”，通过每天一道编程题目来强化和锻炼自己的编程能力（最起码不会忘记编程）

特别说明：编程题来自“牛客网”和“领扣”以及热心小伙伴的题目。由于小白有时想锻炼某一类编程方法，所以提供的代码不一定是最优解，但是本文提供的编程代码均为通过测试代码。

拼凑面额

题目描述

给你六种面额1、5、10、20、50、100元的纸币，假设每种币值的数量都足够多，编写程序求组成N元（N为0-10000的非负整数）的不同组合的个数。

输入描述:

输入为一个数字N，即需要拼凑的面额

输出描述:

输出也是一个数字，为组成N的组合个数。

示例

输入

5

输出

2

解析

最喜欢和钱有关的题目，谁给小白十个亿，小白也能一个月把它花掉。本题其实就是给定一个整数和一个数组，查看有多少种相加的组合方式。我们可以换一种思考方式，比如我们有一张10元钱，其某种组成方式中有一张5元钱，见变成了：（10-5）元钱有多少种组合方式，这样一直循环下去，最后变成0元钱。

利用这种想法，我们可以使用递归的方法来求取结果。但是这里面有一个小小的注意事项，就是递归的循环中后面减去的纸币面值应该大于等于前一次循环的面值。为实现这个需求，需要将当前循环的纸币面值也传入下一次递归中。

代码

#include <iostream>
#include <vector>

using namespace std;

class Solution
{
public:
 
 int count = 0;
 vector<int> money;
 Solution(){};
 Solution(vector<int> money_) :money(money_){}
 void kindofway(int sum, int i)
 {
   int index = money.size();
   for (; i < index; i++)
   {
     int last = sum - money[i];
     if (last==0)
     {
       count++;
       break;
     }
     else if (last>0)
     {
       kindofway(last, i);
     }
     else
     {
       break;
     }
   }
 }

private:

};

int main()
{
 int sum;
 vector<int> money = { 1, 5, 10, 20, 50, 100 };
 while (cin>>sum)
 {
   Solution solution(money);
   solution.kindofway(sum, 0);
   int count = solution.count;
   cout << count << endl;
 }
 return 0;
}