查找总和为特定值的所有子集。找到总和为特定值的所有子集。递归还是DP？
给定一组数字：{1,3,9,12}和目标值= 12。找到与目标值相加的不同子集。
ANS：[3,9]，[12]。
The problem has been asked here.
明明有解决这种问题的两种方法。递归或DP。 问题：你如何权衡这两种方法？
我的解决方案：DP比较困难，但消耗的内存较少。在递归中，你必须多次递归地调用该函数，这引入了头部功能。但它“相当”容易，但消耗更多的内存。
你们认为什么？
通常，没有任何类型缓存的递归可以导致指数复杂度问题的解决方案，这个问题可以用多项式或线性复杂度来解决。这是因为你多次计算相同的部分问题。 memoization的递归或迭代解决方案可以通过使用更多内存来降低复杂性。
这就是说，你需要考虑你的输入的约束。对于更大的输入，指数解决方案通常是无用的，所以你没有太多的选择。同时，在大多数情况下使用额外内存并不是真正的问题，除非您为内存非常有限的系统开发某些内容（如嵌入式系统）。总之，在大多数情况下，您会想要为了算法的复杂性而折衷内存，但是您需要根据具体情况来决定。
我猜DP可以通过递归或基于方法（自上而下或自下而上）的迭代实现。 通用递归解决方案与DP之间的主要区别在于是否需要使用额外的内存，这将是算法运行时间的折衷。基本上，您通过存储和引用额外的计算来避免这种情况。
对于这个问题一般递归或DP，权衡将是通用的递归在DP VS 运行使用内存之间。
要考虑的另一件事情并不是所有的问题都符合DP方法。 所考虑的问题，具有下列性质
上述2个属性对于DP实现是必需的。否则DP不会给你任何优化。
例如：大多数分而治之方法没有“重叠子问题”属性。二进制搜索没有。
希望它有帮助！
DP实际上会消耗更多内存，但它可以让您大量减少冗余（不必要的重复）计算次数。 – ruakh