该问题简化为0-1背包问题，您尝试在其中找到具有精确总和的集合。解决方案取决于约束条件，一般情况下，此问题是NP-
Complete。
但是，如果最大搜索总和（称为
S）不太高，则可以使用动态编程解决问题。我将使用递归函数和备忘录对其进行解释，这比自下而上的方法更容易理解。
让我们对一个函数进行编码
f(v, i,S)，以使其返回
v[i:]恰好等于的子集数
S。为了递归地解决它，首先我们必须分析基数（即：
v[i:]为空）：
S == 0：的唯一子集的
[]
总和为0，因此它是有效子集。因此，该函数应返回1。S！= 0：由于的唯一子集的
[]
总和为0，因此没有有效的子集。因此，该函数应返回0。
然后，让我们分析递归情况（即：
v[i:]不为空）。有两种选择：将数字包括
v[i]在当前子集中，或不包括。如果包含
v[i]，那么我们正在寻找具有sum的子集
S- v[i]，否则，我们仍在寻找具有sum的子集
S。该功能
f可以通过以下方式实现：
def f(v, i, S): if i >= len(v): return 1 if S == 0 else 0 count = f(v, i + 1, S) count += f(v, i + 1, S - v[i]) return countv = [1, 2, 3, 10]sum = 12print(f(v, 0, sum))
通过检查
f(v, 0, S) > 0，您可以知道是否有解决问题的方法。但是，此代码太慢，每个递归调用都产生两个新的调用，从而导致O（2 ^
n）算法。现在，我们可以应用备忘录以使其在时间O（n *S）中运行，如果
S不是太大，它将更快：
def f(v, i, S, memo): if i >= len(v): return 1 if S == 0 else 0 if (i, S) not in memo: # <-- Check if value has not been calculated. count = f(v, i + 1, S, memo) count += f(v, i + 1, S - v[i], memo) memo[(i, S)] = count # <-- Memoize calculated result. return memo[(i, S)] # <-- Return memoized value.v = [1, 2, 3, 10]sum = 12memo = dict()print(f(v, 0, sum, memo))
现在，可以对
g返回一个总和的子集的函数进行编码
S。为此，仅在至少有一个包含元素的解决方案时才添加元素就足够了：
def f(v, i, S, memo): # ... same as before ...def g(v, S, memo): subset = [] for i, x in enumerate(v): # Check if there is still a solution if we include v[i] if f(v, i + 1, S - x, memo) > 0: subset.append(x) S -= x return subsetv = [1, 2, 3, 10]sum = 12memo = dict()if f(v, 0, sum, memo) == 0: print("There are no valid subsets.")else: print(g(v, sum, memo))免责声明：此解决方案表示[10，10]有两个子集，总和为10。这是因为它假定前十个与后十个不同。可以将算法固定为假定两个十个相等（并因此回答一个），但这有点复杂。
