#include <iostream>
#include <vector>
usingnamespace std;
vector<int> vec;
constint a[4] = {1, 2, 5, 10};
//1，2，5，10四个基数任意次数组合相加得到一个数N，求所有可能组合。
//回溯，背包问题
void backup(int N)//总共k个数，和为N
{
if (N == 0)
{
vector<int>::iterator it = vec.begin();
for (; it != vec.end(); ++it)
cout<< *it <<" ";
cout<<endl;
return;
}
if (N < 0) return;
for (int i = 0; i < 4; ++i)
{
//vec.back(),传回最后一个数据，不检查这个数据是否存在
if (vec.empty() || a[i] >= vec.back())// 非降序,为了去掉重复的组合
{
vec.push_back(a[i]);
backup(N-a[i]);
vec.pop_back();
}
}
}
int main(int argc, char* argv[])
{
backup(20);
return 0;
}