递归子集求和函数
recursive subset sum function
我们的教授为我们的 class 递归分享了以下 Python 代码。这是 'subset sum' 问题的解决方案。
我一遍又一遍地阅读它并尝试检查它并使用在线工具逐步按照参数进行操作，但我根本不明白。
我知道代码会检查列表 L 的子集是否有可能使总和为 0，但我不明白该函数到底是如何检查总和是否实际上为 0 的。简单地说：我没有看到任何地方都使用了 sum 函数，所以代码怎么知道子集的元素之和为 0.
def possible(L,som=0,used=False):
if L==[]:
return (som==0) and used
else:
return (possible(L[1:],som,used) or possible(L[1:],som-L[0],True))
我知道有一些关于 subset-sum 与 Python 结合使用的问题，我也看到过一个类似的函数，但是没有相关的解释（至少我没有理解） ).
总结
def possible(L,som=0,used=False):
if the list is empty:
return (is our running sum 0 and have we used at least one element?)
else:
return (what if we ignore the first element?) or \
(what if we use the first element?)
基本思路
此代码基于这样的想法，即 L 中的每个元素都必须在任何可能的子集中或不在任何可能的子集中；没有第三种选择。这非常有用，因为我们确切地知道在这两种情况下我们应该做什么。我们要么在总和中包含该元素，要么不包含该元素。这个和是一步步计算出来的，存入som中。变量名 sum 没有被使用，因为 sum 已经是一个 Python 函数（您似乎已经知道）。代码在 som 重命名为 sum 时仍然有效，但这是糟糕的编码习惯。这两种情况由如下所示的两个递归调用表示：
案例一：
此调用测试第一个元素未包含在子集中的情况。
possible(L[1:],som,used)
我们使用 L[1:] 从任何进一步检查中排除第一个元素。第一个元素未被使用，因此它不会以任何方式改变总和。因此，没有对 som 进行任何更改，而是按原样传递。最后，used 没有改变。我将在 post 中进一步讨论。
案例二：
此调用测试第一个元素 是 包含在子集中的情况。
possible(L[1:],som-L[0],True)
和以前一样，我们不想再次检查第一个元素，所以我们递归 L[1:]。我们是使用L[0]，所以它必须以某种方式改变当前总和（som）。你的教授选择减去它，但如果他将它加起来，它的效果是一样的。 used 现在变成 True。
那么used这是什么废话，当列表为空时我们为什么要关心它？
一个引导性问题，一个空子集的所有元素的总和是多少？就个人而言，我首先想到的是 0。但这是一个问题，因为空集是每个列表的子集。这意味着，如果我们将一个空子集的总和视为 0，任何可能的任何集合，无论是否为数字，都会有一个总和为 0 的子集。这将产生更容易的实现：
def possible(L):
return True
但这一点用处也没有。因此，我们应该只考虑使用某些元素的情况，这就是 used 变量出现的地方。一旦包含任何元素，它就会设置为 True，当我们得到到基本情况，用于过滤掉空集情况。
我们的教授为我们的 class 递归分享了以下 Python 代码。这是 'subset sum' 问题的解决方案。
我一遍又一遍地阅读它并尝试检查它并使用在线工具逐步按照参数进行操作，但我根本不明白。
我知道代码会检查列表 L 的子集是否有可能使总和为 0，但我不明白该函数到底是如何检查总和是否实际上为 0 的。简单地说：我没有看到任何地方都使用了 sum 函数，所以代码怎么知道子集的元素之和为 0.
def possible(L,som=0,used=False):
if L==[]:
return (som==0) and used
else:
return (possible(L[1:],som,used) or possible(L[1:],som-L[0],True))
我知道有一些关于 subset-sum 与 Python 结合使用的问题，我也看到过一个类似的函数，但是没有相关的解释（至少我没有理解） ).
总结
def possible(L,som=0,used=False):
if the list is empty:
return (is our running sum 0 and have we used at least one element?)
else:
return (what if we ignore the first element?) or \
(what if we use the first element?)
基本思路
此代码基于这样的想法，即 L 中的每个元素都必须在任何可能的子集中或不在任何可能的子集中；没有第三种选择。这非常有用，因为我们确切地知道在这两种情况下我们应该做什么。我们要么在总和中包含该元素，要么不包含该元素。这个和是一步步计算出来的，存入som中。变量名 sum 没有被使用，因为 sum 已经是一个 Python 函数（您似乎已经知道）。代码在 som 重命名为 sum 时仍然有效，但这是糟糕的编码习惯。这两种情况由如下所示的两个递归调用表示：
案例一：
此调用测试第一个元素未包含在子集中的情况。
possible(L[1:],som,used)
我们使用 L[1:] 从任何进一步检查中排除第一个元素。第一个元素未被使用，因此它不会以任何方式改变总和。因此，没有对 som 进行任何更改，而是按原样传递。最后，used 没有改变。我将在 post 中进一步讨论。
案例二：
此调用测试第一个元素 是 包含在子集中的情况。
possible(L[1:],som-L[0],True)
和以前一样，我们不想再次检查第一个元素，所以我们递归 L[1:]。我们是使用L[0]，所以它必须以某种方式改变当前总和（som）。你的教授选择减去它，但如果他将它加起来，它的效果是一样的。 used 现在变成 True。
那么used这是什么废话，当列表为空时我们为什么要关心它？
一个引导性问题，一个空子集的所有元素的总和是多少？就个人而言，我首先想到的是 0。但这是一个问题，因为空集是每个列表的子集。这意味着，如果我们将一个空子集的总和视为 0，任何可能的任何集合，无论是否为数字，都会有一个总和为 0 的子集。这将产生更容易的实现：
def possible(L):
return True
但这一点用处也没有。因此，我们应该只考虑使用某些元素的情况，这就是 used 变量出现的地方。一旦包含任何元素，它就会设置为 True，当我们得到到基本情况，用于过滤掉空集情况。