问题描述

有 N 枚硬币，面值分别是 a1,a2,..ai,..aN，问可不可以凑成 M？

思路分析

这个题，直接想到的就是遍历，复杂度会非常大，否掉。直观方法如此复杂的问题，通常可以分解成子问题来解决：
考虑 ai，看 a1…ai 这个子序列是否可以组成 M。我们把原问题分解成了子问题，并假设该子问题的子问题，即 a1…ai-1 不能组成 M。为什么这么假设呢？问题分解的求解思路是找一个分解路径，然后实际求的时候从最小的子问题开始算，也就是 a1，然后逐步增大问题规模： a1,a2; a1,a2,a3;… 当到达某个规模的子问题时如果符合条件就终止，不再计算后面更大的子问题。因此既然算到 a1…ai 这个子问题，那么它的更小的子问题当然是没有符合条件。
在解决 a1…ai 这个问题时，需要依赖它的子问题 a1…ai-1 求出的结果。现在问题的关键就是子问题保存了什么。原问题是问是否可以凑成M，那么子问题只保存一个 bool 值是否可以？不可，它没有提供可用的信息。
再想一下，既然原问题的意思是求数组中的数是否可以组合成一个给定的值，那么将原问题的表述稍微改变一下：该数组可以凑成哪些数，有没有一个是M？
现在就知道了，子问题 a1..ai-1 要记录的就是它当前可以组成哪些数。同样，a1..ai 也得求这个信息，而且根据前一子问题来求。到了这步，递推的关系就容易想清楚了：
a1..ai-1 可以组成的数的集合是：Ai-1
a1..ai 可以组成的数的集合由两部分构成：

• Ai-1
• Ai-1 的每个数加上 ai

两个集合可能有相同元素，需要 union 合并一下，就能得到 Ai。
递推关系找到了，需要从最小的子问题开始求。现在需要验证最小的子问题是否可以求A1？显然可以。那么问题就可以这么解决了。

代码

include <set>#include <iostream>using namespace std;bool CombinationProblem(const int* arr, int len, int M ){ if(arr == NULL) return false; set<int> s1, s2; s1.insert(0); // s1 保存前一子问题的组合 s2.clear(); // s2 保存s1加上当前元素后的组合 for (int i=0; i<len; ++i) { for (auto j=s1.begin(); j!=s1.end();++j) { s2.insert(*j + arr[i]); } s1.insert(s2.begin(), s2.end()); s2.clear(); if (s1.end() != s1.find(M)) { return true; } } return false;}void main(){ int testArr[10] = {1, 5, 3, 9, 55, 34, 2, 8, 22, 4}; int M = 99; cout<<CombinationProblem(testArr, 10, M)<<endl;}