1.题目要求在一个数组中，找出和为M的元素。
2.这道题目采用深度遍历，因为M的值<=100，即需求最大是100，因为硬币价值是正数，那么最多需要100个硬币，即进行DFS的深度为100，可以接受
3.需要进行剪枝：
1）把coin价值从小到大排列；
2）从第一个开始遍历，如果价格减去这个硬币的价值后，剩下的价格小于这个硬币的价值，那么可以continue。因为后面的硬币价值都大于等于现在硬币的价值，有一种情况例如，就是价格减去这个硬币的价值后，刚好等于0，那么就可以输出答案；
3）按照上述从小到大排列，第一次获得的答案，肯定为最小的，此时可以直接跳出DFS，输出答案即可。
Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.
Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.
Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].
Sample Input 1:
8 9 5 9 8 7 2 3 4 1
Sample Output 1:
1 3 5
Sample Input 2:
4 8 7 2 4 3
Sample Output 2:
No Solution
AC代码：
//#include<string>
//#include<stack>
//#include<unordered_set>
//#include <sstream>
//#include "func.h"
//#include <list>
#include <iomanip>
#include<unordered_map>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include <algorithm>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
#include<stack>
using namespace std;
void dfs(int nowIdx, int need, vector<int>&coin, vector<int>&solution, vector<vector<int>>&ans)
{
if (need == 0)
{
ans.push_back(solution);
}
else
{
bool hasSolution = false;
if (coin[nowIdx] > need) return;//不用进行下面的遍历，因为nowIdx后面的coin大于或等于现在的coin
for (int i = nowIdx; i < coin.size(); i++)
{
if (hasSolution && coin[i] == coin[i - 1])
continue;//这个硬币方案和上一个方案一样
else
{
if (need - coin[i] < coin[i] && need!=coin[i]) continue;//如果这个硬币选了之后，剩下的价值比这个硬币小，则不可能，因为后面的硬币价值比现在这个大，除非这个硬币刚好等于need
hasSolution = true;
solution.push_back(coin[i]);
dfs(i + 1, need - coin[i], coin, solution, ans);
if (ans.size()) return;//有答案，则这个答案必然是最小的,进行剪枝
solution.pop_back();
}
if (coin[i] == need) break;//这个已经是答案了，后面不可能存在不一样的答案，不用遍历
}
}
}
bool cmp(const vector<int>&a, const vector<int>&b)
{
for (int i = 0; i < min(a.size(), b.size()); i++)
{
if (a[i] < b[i]) return true;
else if (a[i] > b[i]) return false;
}
if (a.size() < b.size()) return true;
else return false;
}
int main(void)
{
int n, need;
cin >> n >> need;
vector<int> coin(n);
for (int i = 0; i < n; i++)
{
scanf("%d", &coin[i]);
}
vector<int> solution(0);
vector<vector<int>> ans(0);
sort(coin.begin(), coin.end());
dfs(0, need, coin, solution, ans);
sort(ans.begin(), ans.end(),cmp);
if (ans.size() == 0)
cout << "No Solution" << endl;
else
{
for (int i = 0; i < ans[0].size(); i++)
{
printf("%d", ans[0][i]);
if (i != ans[0].size() - 1)
printf(" ");
}
cout << endl;
}
return 0;
}