求和组合码

Question

你好，我是 Python 的新手，我正在尝试解决一个编码挑战，其中 objective 是创建一个函数，该函数采用整数数组（负数和正数）和一个目标value（也是一个整数），然后如果数字的任何组合总和为目标值，则输出 true，该目标值将始终大于输入数组中的任何其他单个元素。我试图这样做，但非常失败。我发现别人的代码分两行完成，但我不知道它是如何工作的，希望这里有人能给我指明正确的方向。这是代码

def subsetsum(target, arr):
  if len(arr) == 0:
    return target == 0


  return subsetsum(target, arr[1:]) or subsetsum(target - arr[0], arr[1:])

我的意思是我什至没有看到他们在哪里总结数字并与目标进行比较，我们将不胜感激。提前致谢。

Answer 1

edit 该代码中存在错误（取决于您是否认为 [1] 中的数字组合总和为 0 ).尝试

subsetsum(0,[1])
> True

下面我再解释一下。 结束编辑

所以我认为理解代码的挑战与其说是 Python，不如说是理解递归函数。

让我们假设函数 subsetsum 适用于长度小于 N 的列表。现在让我们取一些长度为 N 的列表。如果有一个子集求和到目标，它要么涉及第一个元素 ( arr[0]) 或者没有。所以我们将把它分成两个问题 - 检查是否有一个子集包含第一个元素，并检查是否有一个子集没有。

注意arr[1:]是一个长度为N-1的数组，从arr的第二个元素开始。

所以如果有一个子集不涉及arr[0]，那么subsetsum(target,arr[1:])就会给出True。如果存在涉及 arr[0] 的子集，则 subsetsum(target-arr[0],arr[1:]) 将 return True。如果两者都不成立，那么它将 return False.

所以基本上这是否适用于 N 取决于它是否适用于 N-1，这取决于它是否适用于 N-2 等。最后我们得到长度 0。如果target为0，此时，应该returnTrue。如果不是，则 False，或者至少，编写此代码的人是这么想的。我不同意。下面的错误说明。

就我个人而言，我认为这段代码中存在错误。如果我给它任何列表和 0 的目标，它将 return True。 ~~测试应该是当它下降到长度为 1 的列表时，目标是否等于那个值。~~测试应该是第一个元素是否是目标，如果它得到到长度为 0 的列表，它失败了。

def subsetsum(target, arr):
  if len(arr)==0:
    return False
  elif arr[0]==target:
    return True    
  else:
    return subsetsum(target, arr[1:]) or subsetsum(target - arr[0], arr[1:])

Answer 2

他们的解决方案使用递归以非常聪明的方式表达所有可能的数字组合。但聪明并不总是意味着可读或易于理解（所有代码都应该如此）所以不要因为没有马上得到它而难过。就个人而言，我不会考虑这个好代码。

最简单的方法就是逆向计算。

如果 arr 有 0 个元素会怎样？好吧，它在函数的开头明确检查了：如果target已经是0，它只能是问题的解决方案。让我们参考subsetsum的这种特殊情况（其中arr是 []) 和 is_zero，因为它就是这样做的。
如果 arr 有 1 个元素 [x] 会怎样？对于存在的解决方案，您必须通过在总和中包含或不包含 x 来获得 target。这是通过将问题转换为 0 元素版本来完成的，因为 arr[1:] 将是空列表 ([])。 or 表达式的第一部分 subsetsum(target, arr[1:]) 忽略了 x 并且基本上询问是否 is_zero(target)。表达式的第二部分通过询问是否 is_zero(target - x) 在总和中包含 x。用 arr = [9] 试试。如果 is_zero(target) 或 is_zero(target - 9)，你会得到 True。这有道理，对吧？如果目标是0或9，那么[0]或[9]分别是问题的解。
如果 arr 有 2 个元素 [x, y] 会怎样？同样，问题被简化为 1 个元素更小的版本，因为 arr[1:] 只是 [y]。那么，subsetsum(target, [y]) 中是否有解决方案或 subsetsum(target - x, [y]) 中是否有解决方案？用 [3, 9] 试试。表达式的第一部分忽略 3 并在 target 为 9 或 0 时计算 True。第二部分包括 3 并在 target - 3 为 9 或 0 时计算 True（即如果 target 是 12 或 3)。因此，它 "tries" 所有可能的组合：[]、[9]、[3] 和 [9, 3]。
subsetsum(target, [x, y, z]) 缩减为 subsetsum(target, [y, z]) 或 subsetsum(target - x, [y, z])，依此类推...

现在从上往下看，对于 arr 中的每个元素，问题被拆分为 "is there a solution if we do not include this element?" 和 "is there a solution if we do include this element?" 两个子问题这样，你就结束了尝试所有 2**len(arr) 组合。

使用 Python 非常棒的模块 itertools 绝对可以解决这个问题，但我现在没时间写.不过，我明天可能会尝试一下，只是为了好玩。

编辑：这是我的更具可读性（并且可能更快）的版本。

import itertools

def subsetsum(target, arr):
    for subset_len in range(len(arr) + 1):
        if any(sum(subset) == target for subset in itertools.combinations(arr, subset_len)):
            return True
    return False

它只是找到所有子集，从长度 0（所以 []）开始，一直到长度 len(arr)，并检查是否有任何子集的总和为 target。 Python 是一门美丽的语言！

求和组合码

Summation Combination code

python

combinatorics