Python：找到最短的数字列表，添加后将是特定数字
Python: find shortest list of numbers which when added would be a specific number
正如标题所说：
要编写的函数有 2 个参数，第一个是数字，第二个是数字列表：
示例：(7, [5,3,4,7])
要编写的 Python 函数应该 return 一个数字列表，添加后会导致“7”
例如 [3,4] 或 [4,3] 或 [7]
我写了一个 Python 函数，它确实有效（见下面的 bestSum()），但它只有 returns 1 个工作组合，我希望有人可以帮助编辑它，这样它将 return 所有可能的“好”组合。那我可以select最短的
递归Python函数是用二叉树往下走，从列表中减去一个数到主数（减去相同的数是可以的）。如果最后一个节点中有 0，那么它是赢家，但如果结果为负，那么它是不可能的组合，应该被删除。
所以不只是 returning，假设 [4,3]，而是 return：
([3,4], [4,3], [7])
或者至少帮我改变循环，这样它在找到第一个有效组合后就不会停止。
def bestSum(nb, intlist, res=[[], []]):
if (nb == 0):
res[0] = True
return res
if (nb < 0):
res[0] = False
return res
for i in intlist:
remainder = nb - i
res = bestSum(remainder, intlist, res)
if (res[0] == True):
res[1].append(i)
res[0] = True
return res
res[0] = False
return res
现在这两行代码
res = bestSum(7, [5,3,4,7])
print("Shortest Result list is = ", res[1])
将return:
Shortest Result list is = [4, 3]
(其实不是最短的，应该是[7])
注意：这与硬币找零问题不同，因为硬币问题也包括美分并且总是有解决方案，而这里我们没有。
所以这里并不总是有解决方案，例如在 (7, [4,5]) 的情况下，没有 4 和 5 的组合可以添加到 7.
谢谢
潜在的问题是：
I have a recursive algorithm. When I make one or more recursive calls, I want to collect the results from those recursive calls, and use them to produce the result for this level of the recursion. (Simplest case: I want a list of all the recursive results.) How can I accomplish this simply?
当我们不依赖任何副作用或可变数据结构时，推理递归算法要容易得多。修改列表 - 尤其是 when they are default parameters being used as a cache - 很快就会让人头疼。即使我们从递归调用中得到一些不可变的数据（比如 tuple）并想合并这些结果，通常也很尴尬。 （可能很难记住，例如，某些叶结果应该是 () 或单例元组，而不是 None 或特定元素值。）
我推荐的绕过这个的方法是使用递归生成器。然而，我想展示几种方法，以解释递归算法的一些通用技术。
让我们首先考虑按深度优先顺序列出树中所有节点的简单示例：
def all_nodes_at(root):
# If this is a leaf node, then `root.children` is empty;
# so the loop will simply not run and nothing is yielded.
for child in root.children:
yield from all_nodes_at(child)
yield root # include the current node, after all nodes underneath.
# To see the results, we need to iterate over the generator in some way:
tree_nodes = list(all_nodes_at(tree_root))
将其与使用元组的方法进行比较：
def all_nodes_at(root):
result = ()
for child in root.children:
result = result + all_nodes_at(child)
return result + (root,)
tree_nodes = all_nodes_at(tree_root)
我觉得更难看。使用列表缓存：
def all_nodes_at(root, cache=[]):
for child in root.children:
cache.extend(all_nodes_at(child))
cache.append(root)
return cache
tree_nodes = all_nodes_at(tree_root)
哎呀。我们不仅被迫 return 一个我们在递归中实际没有使用的值（以便我们在顶层得到一个结果），而且如果我们想多次使用它就会中断。 “哦，没关系，我们先清一下缓存就好了。”真的吗？您想记录用户在调用该函数之前需要执行 all_nodes_at.__defaults__[0].clear() 吗？当然最好不要默认参数。如果它不是默认参数并且用户提供初始缓存会更好：
def dump_all_nodes_at(root, cache):
for child in root.children:
cache.extend(all_nodes_at(child))
cache.append(root)
tree_nodes = []
dump_all_nodes_at(tree_root, tree_nodes)
至少这是可重用的，我们不必玩 return 值的傻游戏（事实上，我们根本不需要 return）。但是现在这个界面真的很尴尬。
你可以看出为什么我通常更喜欢递归生成器。
让我们将该技术应用于查找具有给定总和的所有子集的问题。但首先，我们需要清楚地思考递归算法。我们实际上不想在算法的给定步骤中尝试每个元素。为什么？因为如果我们只尝试第一个元素，那么其他元素 将由递归中的后续步骤处理 。当然，这意味着我们不会获得给定结果集的所有可能排序；但我们稍后可以用例如itertools.permutations 如果真的很重要。 （此外，我很确定您的方法不会阻止多次使用同一元素。）
简单的定义如下：给定总和的子集要么包含第一个元素，要么不包含。我们的子集包括
- 我们决定包含的先前递归级别的元素；
- 可能是当前元素；
- 来自对剩余元素的递归调用的元素。
我们要做的是在适当的地方将当前元素添加到递归调用的结果中（即，我们用较小的目标总和递归调用的结果）。当我们通过递归冒泡时，其他元素将自动添加到前面。
因此：
def subsets_with_sum(values, target):
if target < 0:
# There are no solutions, so bail out.
return
if not values:
# Nesting the check like this allows for zeros in `values`.
if target == 0:
# We have reached the trivial solution.
yield ()
# No current element, therefore no more solutions.
return
# Otherwise, we recurse twice, yielding sub-results.
# First, some useful renaming
this_value, *other_values = values
for subset in subsets_with_sum(other_values, target - this_value):
yield (this_value,) + subset # prepend and yield it back
# `yield from` is sugar for iterating and yielding each result directly.
yield from subsets_with_sum(other_values, target)
我们来测试一下：
>>> list(subsets_with_sum([5,4,3,7], 7))
[(4, 3), (7,)]
>>> list(subsets_with_sum(range(10), 10))
[(0, 1, 2, 3, 4), (0, 1, 2, 7), (0, 1, 3, 6), (0, 1, 4, 5), (0, 1, 9), (0, 2, 3, 5), (0, 2, 8), (0, 3, 7), (0, 4, 6), (1, 2, 3, 4), (1, 2, 7), (1, 3, 6), (1, 4, 5), (1, 9), (2, 3, 5), (2, 8), (3, 7), (4, 6)]
根据问题中的评论，我们可以在 intlist 多次 中选择相同的元素以形成总和为给定 target.
迭代解决方案
这里我们逐步遍历 intlist 中的不同值并构建一个新的组合，总和为给定的总和，然后在其中添加新数字。
def bestSum(target, intlist):
# initialize the dp dict
dp = {} # dp[combinationSum] = combination
for num in intlist:
dp[num] = [num]
# max steps we would need to arrive at a valid combination(if it exists) would be
# the combination containing only the min element in the intlist
# e.g. for target = 20 and intlist = [2,7], if we don't find a valid combination within
# 10 steps(all 2's), no valid answer would exist
for step in range(target//min(intlist) + 1):
for combinationSum, combination in dp.copy().items(): # avoid modifying the dict while itrating
for i in intlist:
newSum = combinationSum + i
if newSum == target:
# since we are taking a step one at a time, the first sum being equal to target
# will guarantee a shortest combination
return combination + [i]
if newSum > target:
# skip if newSum if over target(skip adding additional entries into dp to improve perf)
continue
if not dp.get(newSum):
# if the dp already has an non-zero length list in it = its length is going to be
# at least equal to new combination length or lower, so we don't need to overwrite it
dp[newSum] = combination + [i]
target, intlist = 20, [5,3,4,7]
print(bestSum(target, intlist))
打印
[5, 5, 5, 5]
为简单起见，这是我们在 dp 中的每个步骤 intlist = [5,3,4,7] 和 20 -
的目标
Step : 0 - dp: {3: [3], 4: [4], 5: [5], 7: [7]}
Step : 1 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 14: [7, 7]}
Step : 2 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7]}
Step : 3 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7], 20: [5, 5, 5, 5]}
递归求解
如果你想坚持使用递归方法，你可以对你的原始代码做一些小的改动，使其return所有组合总和达到所需的目标。
首先，我们不需要创建函数 return True/False，相反我们可以 return None 以防没有有效组合总和为目标值。
我们想要收集总和为所需值的所有组合，因此我们不应该 return 在找到有效组合时调用函数，而是将其保存在我们以后可以访问的地方。
combinations = []
def bestSum(target, intlist, res=[]):
if (target == 0):
# found a valid combination
combinations.append(res) # collect the current combinations - THIS is what you were looking for
return
if (target < 0):
return
for i in intlist:
remainder = target - i
bestSum(remainder, intlist, res + [i])
target, intlist = 20, [5, 4, 3, 7]
bestSum(target, intlist)
print(combinations, len(combinations))
现在所有与目标相加的组合都写入了组合，但这有一些问题..
以上代码打印 -
[[5, 5, 5, 5], [5, 5, 4, 3, 3], [5, 5, 3, 4, 3], [5, 5, 3, 3, 4], [5, 5, 3, 7], [5, 5, 7, 3], [5, 4, 5, 3, 3], [5, 4, 4, 4, 3], [5, 4, 4, 3, 4], [5, 4, 4, 7], [5, 4, 3, 5, 3], [5, 4, 3, 4, 4], [5, 4, 3, 3, 5], [5, 4, 7, 4], [5, 3, 5, 4, 3], [5, 3, 5, 3, 4], [5, 3, 5, 7], [5, 3, 4, 5, 3], [5, 3, 4, 4, 4], [5, 3, 4, 3, 5], [5, 3, 3, 5, 4], [5, 3, 3, 4, 5], [5, 3, 3, 3, 3, 3], [5, 3, 7, 5], [5, 7, 5, 3], [5, 7, 4, 4], [5, 7, 3, 5], [4, 5, 5, 3, 3], [4, 5, 4, 4, 3], [4, 5, 4, 3, 4], [4, 5, 4, 7], [4, 5, 3, 5, 3], [4, 5, 3, 4, 4], [4, 5, 3, 3, 5], [4, 5, 7, 4], [4, 4, 5, 4, 3], [4, 4, 5, 3, 4], [4, 4, 5, 7], [4, 4, 4, 5, 3], [4, 4, 4, 4, 4], [4, 4, 4, 3, 5], [4, 4, 3, 5, 4], [4, 4, 3, 4, 5], [4, 4, 3, 3, 3, 3], [4, 4, 7, 5], [4, 3, 5, 5, 3], [4, 3, 5, 4, 4], [4, 3, 5, 3, 5], [4, 3, 4, 5, 4], [4, 3, 4, 4, 5], [4, 3, 4, 3, 3, 3], [4, 3, 3, 5, 5], [4, 3, 3, 4, 3, 3], [4, 3, 3, 3, 4, 3], [4, 3, 3, 3, 3, 4], [4, 3, 3, 3, 7], [4, 3, 3, 7, 3], [4, 3, 7, 3, 3], [4, 7, 5, 4], [4, 7, 4, 5], [4, 7, 3, 3, 3], [3, 5, 5, 4, 3], [3, 5, 5, 3, 4], [3, 5, 5, 7], [3, 5, 4, 5, 3], [3, 5, 4, 4, 4], [3, 5, 4, 3, 5], [3, 5, 3, 5, 4], [3, 5, 3, 4, 5], [3, 5, 3, 3, 3, 3], [3, 5, 7, 5], [3, 4, 5, 5, 3], [3, 4, 5, 4, 4], [3, 4, 5, 3, 5], [3, 4, 4, 5, 4], [3, 4, 4, 4, 5], [3, 4, 4, 3, 3, 3], [3, 4, 3, 5, 5], [3, 4, 3, 4, 3, 3], [3, 4, 3, 3, 4, 3], [3, 4, 3, 3, 3, 4], [3, 4, 3, 3, 7], [3, 4, 3, 7, 3], [3, 4, 7, 3, 3], [3, 3, 5, 5, 4], [3, 3, 5, 4, 5], [3, 3, 5, 3, 3, 3], [3, 3, 4, 5, 5], [3, 3, 4, 4, 3, 3], [3, 3, 4, 3, 4, 3], [3, 3, 4, 3, 3, 4], [3, 3, 4, 3, 7], [3, 3, 4, 7, 3], [3, 3, 3, 5, 3, 3], [3, 3, 3, 4, 4, 3], [3, 3, 3, 4, 3, 4], [3, 3, 3, 4, 7], [3, 3, 3, 3, 5, 3], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5], [3, 3, 3, 7, 4], [3, 3, 7, 4, 3], [3, 3, 7, 3, 4], [3, 3, 7, 7], [3, 7, 5, 5], [3, 7, 4, 3, 3], [3, 7, 3, 4, 3], [3, 7, 3, 3, 4], [3, 7, 3, 7], [3, 7, 7, 3], [7, 5, 5, 3], [7, 5, 4, 4], [7, 5, 3, 5], [7, 4, 5, 4], [7, 4, 4, 5], [7, 4, 3, 3, 3], [7, 3, 5, 5], [7, 3, 4, 3, 3], [7, 3, 3, 4, 3], [7, 3, 3, 3, 4], [7, 3, 3, 7], [7, 3, 7, 3], [7, 7, 3, 3]] 123
仅仅为了 20 的一个小目标，就有多达 123 种组合。如果您浏览组合列表，您会注意到 combinations 包括给定有效组合的所有排列，从而导致这种臃肿的大小。该代码还必须做额外的工作来导出所有这些组合。
我们可以做些什么来避免这些重复？
排序来拯救;如果我们确保每个有效组合始终排序，则最终 combinations 中不能有相同组合的排列。如何在代码中利用这一点？
combinations = []
def bestSum(target, intlist, combination=[]):
if (target == 0):
# found a valid combination
combinations.append(combination)
return
if (target < 0):
return
for i in intlist[::-1]:
# each combination will be in ascending order
# while i is in descending order here, so if last element in my
# combination is greater than i, we can break the loop to stop
# additional work, and make sure that all the combinations are unique
if combination and combination[-1] > i:
break
remainder = target - i
bestSum(remainder, intlist, combination + [i])
target, intlist = 20, [5, 4, 3, 7]
bestSum(target, sorted(intlist)) # sort list of values
print(combinations, len(combinations))
这个输出
[[5, 5, 5, 5], [4, 4, 5, 7], [4, 4, 4, 4, 4], [3, 5, 5, 7], [3, 4, 4, 4, 5], [3, 3, 7, 7], [3, 3, 4, 5, 5], [3, 3, 3, 4, 7], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5]] 10
现在，我们的组合中没有任何排列！我们可以很容易地从 combinations.
中得到所有需要的 shortest/longest 组合
但是正如@karl 在他的回答中所指出的，这个接口看起来很糟糕，我们实际上应该使用递归生成器来使接口更清晰。看起来像这样 -
def bestSum(target, intlist, combination=[]):
if (target == 0):
# found a valid combination
yield combination
if (target < 0):
return
for i in intlist[::-1]:
if combination and combination[-1] > i:
break
remainder = target - i
yield from bestSum(remainder, intlist, combination + [i])
target, intlist = 20, [5, 4, 3, 7]
intlist.sort()
targetCombinations = list(bestSum(target, intlist))
targetCombinations.sort(key=lambda x: len(x))
print("One of the shortest combination - ", targetCombinations[0])
使用递归仅返回最短路径之一 - 仅使用 return 和使用单个递归函数是不可能的，因为一旦我们 return 一个值，我们将无法继续搜索剩余的组合。因此，解决此问题的一种方法是将递归函数包装在另一个函数中，并使 return 成为您在完成所有组合后遇到的最短组合或使用全局变量（我会避免采用全局变量方式) 或通过引用原始函数传递变量。
def shortestCombinationSum(target, intlist, combination=[]):
shortest = None
def bestSum(target, intlist, combination):
nonlocal shortest
if (target == 0 and (not shortest or len(combination) < len(shortest))):
# found a valid combination which is shorter
shortest = combination
return
if (target < 0):
return
for i in intlist[::-1]:
if combination and combination[-1] > i:
break
remainder = target - i
bestSum(remainder, intlist, combination + [i])
bestSum(target, intlist, combination)
return shortest
target, intlist = 20, [5, 4, 3, 7]
print(shortestCombinationSum(target, sorted(intlist)))
虽然这使函数看起来很奇怪，但 shortestCombinationSum 的界面相当干净。另一种选择可能是将 shortest 作为全局变量然后不断更新它，在这种情况下我们不必将函数包装在另一个函数中，但我们必须清除全局变量的值如果我们用不同的输入集一遍又一遍地调用函数。
我仍然会推荐迭代解决方案而不是上面的递归解决方案，因为给定大小 n 的 intlist，您在图表中的树将是 n-ary tree，具有每个节点上的 n 个分支从顶部的 target 开始。迭代解类似于 n 叉树中的层次顺序遍历，当它到达找到解的层次时将停止。虽然递归解决方案是树上的 DFS，但它需要遍历 n 叉树的每个组合（修剪重复排列）。
这是一个简单的：
import itertools as it
# create all possible route
def create_permutation(data):
final = []
for k in range(1, len(data) + 1):
temp = list(it.permutations(data, k))
final.extend(temp)
return final
# find best sum in equal to num
def best_sum(subs, num, _min = True):
final = []
for i in range(len(subs)):
temp_sums = sum(subs[i])
if temp_sums == num:
final.append(subs[i])
if not final:
return None
# if only wants minimum then sort by length then return first
if _min:
return sorted(final, key = lambda x : len(x))[0]
return final
def main(data, num):
subs = create_permutation(data)
result = best_sum(subs, num, False)
print("Best === ", result)
data = [5, 3, 4, 7, 2]
num = 7
main(data, num)
正如标题所说： 要编写的函数有 2 个参数，第一个是数字，第二个是数字列表：
示例：(7, [5,3,4,7]) 要编写的 Python 函数应该 return 一个数字列表，添加后会导致“7” 例如 [3,4] 或 [4,3] 或 [7]
我写了一个 Python 函数，它确实有效（见下面的 bestSum()），但它只有 returns 1 个工作组合，我希望有人可以帮助编辑它，这样它将 return 所有可能的“好”组合。那我可以select最短的
递归Python函数是用二叉树往下走，从列表中减去一个数到主数（减去相同的数是可以的）。如果最后一个节点中有 0，那么它是赢家，但如果结果为负，那么它是不可能的组合，应该被删除。
所以不只是 returning，假设 [4,3]，而是 return： ([3,4], [4,3], [7]) 或者至少帮我改变循环，这样它在找到第一个有效组合后就不会停止。
def bestSum(nb, intlist, res=[[], []]):
if (nb == 0):
res[0] = True
return res
if (nb < 0):
res[0] = False
return res
for i in intlist:
remainder = nb - i
res = bestSum(remainder, intlist, res)
if (res[0] == True):
res[1].append(i)
res[0] = True
return res
res[0] = False
return res
现在这两行代码
res = bestSum(7, [5,3,4,7])
print("Shortest Result list is = ", res[1])
将return:
Shortest Result list is = [4, 3]
(其实不是最短的，应该是[7])
注意：这与硬币找零问题不同，因为硬币问题也包括美分并且总是有解决方案，而这里我们没有。 所以这里并不总是有解决方案，例如在 (7, [4,5]) 的情况下，没有 4 和 5 的组合可以添加到 7.
谢谢
潜在的问题是：
I have a recursive algorithm. When I make one or more recursive calls, I want to collect the results from those recursive calls, and use them to produce the result for this level of the recursion. (Simplest case: I want a list of all the recursive results.) How can I accomplish this simply?
当我们不依赖任何副作用或可变数据结构时，推理递归算法要容易得多。修改列表 - 尤其是 when they are default parameters being used as a cache - 很快就会让人头疼。即使我们从递归调用中得到一些不可变的数据（比如 tuple）并想合并这些结果，通常也很尴尬。 （可能很难记住，例如，某些叶结果应该是 () 或单例元组，而不是 None 或特定元素值。）
我推荐的绕过这个的方法是使用递归生成器。然而，我想展示几种方法，以解释递归算法的一些通用技术。
让我们首先考虑按深度优先顺序列出树中所有节点的简单示例：
def all_nodes_at(root):
# If this is a leaf node, then `root.children` is empty;
# so the loop will simply not run and nothing is yielded.
for child in root.children:
yield from all_nodes_at(child)
yield root # include the current node, after all nodes underneath.
# To see the results, we need to iterate over the generator in some way:
tree_nodes = list(all_nodes_at(tree_root))
将其与使用元组的方法进行比较：
def all_nodes_at(root):
result = ()
for child in root.children:
result = result + all_nodes_at(child)
return result + (root,)
tree_nodes = all_nodes_at(tree_root)
我觉得更难看。使用列表缓存：
def all_nodes_at(root, cache=[]):
for child in root.children:
cache.extend(all_nodes_at(child))
cache.append(root)
return cache
tree_nodes = all_nodes_at(tree_root)
哎呀。我们不仅被迫 return 一个我们在递归中实际没有使用的值（以便我们在顶层得到一个结果），而且如果我们想多次使用它就会中断。 “哦，没关系，我们先清一下缓存就好了。”真的吗？您想记录用户在调用该函数之前需要执行 all_nodes_at.__defaults__[0].clear() 吗？当然最好不要默认参数。如果它不是默认参数并且用户提供初始缓存会更好：
def dump_all_nodes_at(root, cache):
for child in root.children:
cache.extend(all_nodes_at(child))
cache.append(root)
tree_nodes = []
dump_all_nodes_at(tree_root, tree_nodes)
至少这是可重用的，我们不必玩 return 值的傻游戏（事实上，我们根本不需要 return）。但是现在这个界面真的很尴尬。
你可以看出为什么我通常更喜欢递归生成器。
让我们将该技术应用于查找具有给定总和的所有子集的问题。但首先，我们需要清楚地思考递归算法。我们实际上不想在算法的给定步骤中尝试每个元素。为什么？因为如果我们只尝试第一个元素，那么其他元素 将由递归中的后续步骤处理 。当然，这意味着我们不会获得给定结果集的所有可能排序；但我们稍后可以用例如itertools.permutations 如果真的很重要。 （此外，我很确定您的方法不会阻止多次使用同一元素。）
简单的定义如下：给定总和的子集要么包含第一个元素，要么不包含。我们的子集包括
- 我们决定包含的先前递归级别的元素；
- 可能是当前元素；
- 来自对剩余元素的递归调用的元素。
我们要做的是在适当的地方将当前元素添加到递归调用的结果中（即，我们用较小的目标总和递归调用的结果）。当我们通过递归冒泡时，其他元素将自动添加到前面。
因此：
def subsets_with_sum(values, target):
if target < 0:
# There are no solutions, so bail out.
return
if not values:
# Nesting the check like this allows for zeros in `values`.
if target == 0:
# We have reached the trivial solution.
yield ()
# No current element, therefore no more solutions.
return
# Otherwise, we recurse twice, yielding sub-results.
# First, some useful renaming
this_value, *other_values = values
for subset in subsets_with_sum(other_values, target - this_value):
yield (this_value,) + subset # prepend and yield it back
# `yield from` is sugar for iterating and yielding each result directly.
yield from subsets_with_sum(other_values, target)
我们来测试一下：
>>> list(subsets_with_sum([5,4,3,7], 7))
[(4, 3), (7,)]
>>> list(subsets_with_sum(range(10), 10))
[(0, 1, 2, 3, 4), (0, 1, 2, 7), (0, 1, 3, 6), (0, 1, 4, 5), (0, 1, 9), (0, 2, 3, 5), (0, 2, 8), (0, 3, 7), (0, 4, 6), (1, 2, 3, 4), (1, 2, 7), (1, 3, 6), (1, 4, 5), (1, 9), (2, 3, 5), (2, 8), (3, 7), (4, 6)]
根据问题中的评论，我们可以在 intlist 多次 中选择相同的元素以形成总和为给定 target.
迭代解决方案
这里我们逐步遍历 intlist 中的不同值并构建一个新的组合，总和为给定的总和，然后在其中添加新数字。
def bestSum(target, intlist):
# initialize the dp dict
dp = {} # dp[combinationSum] = combination
for num in intlist:
dp[num] = [num]
# max steps we would need to arrive at a valid combination(if it exists) would be
# the combination containing only the min element in the intlist
# e.g. for target = 20 and intlist = [2,7], if we don't find a valid combination within
# 10 steps(all 2's), no valid answer would exist
for step in range(target//min(intlist) + 1):
for combinationSum, combination in dp.copy().items(): # avoid modifying the dict while itrating
for i in intlist:
newSum = combinationSum + i
if newSum == target:
# since we are taking a step one at a time, the first sum being equal to target
# will guarantee a shortest combination
return combination + [i]
if newSum > target:
# skip if newSum if over target(skip adding additional entries into dp to improve perf)
continue
if not dp.get(newSum):
# if the dp already has an non-zero length list in it = its length is going to be
# at least equal to new combination length or lower, so we don't need to overwrite it
dp[newSum] = combination + [i]
target, intlist = 20, [5,3,4,7]
print(bestSum(target, intlist))
打印
[5, 5, 5, 5]
为简单起见，这是我们在 dp 中的每个步骤 intlist = [5,3,4,7] 和 20 -
Step : 0 - dp: {3: [3], 4: [4], 5: [5], 7: [7]}
Step : 1 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 14: [7, 7]}
Step : 2 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7]}
Step : 3 - dp: {3: [3], 4: [4], 5: [5], 6: [3, 3], 7: [7], 8: [5, 3], 9: [5, 4], 10: [5, 5], 11: [4, 7], 12: [5, 7], 13: [5, 5, 3], 14: [7, 7], 15: [5, 5, 5], 16: [5, 4, 7], 17: [5, 5, 7], 18: [4, 7, 7], 19: [5, 7, 7], 20: [5, 5, 5, 5]}
递归求解
如果你想坚持使用递归方法，你可以对你的原始代码做一些小的改动，使其return所有组合总和达到所需的目标。
首先，我们不需要创建函数 return True/False，相反我们可以 return None 以防没有有效组合总和为目标值。
我们想要收集总和为所需值的所有组合，因此我们不应该 return 在找到有效组合时调用函数，而是将其保存在我们以后可以访问的地方。
combinations = []
def bestSum(target, intlist, res=[]):
if (target == 0):
# found a valid combination
combinations.append(res) # collect the current combinations - THIS is what you were looking for
return
if (target < 0):
return
for i in intlist:
remainder = target - i
bestSum(remainder, intlist, res + [i])
target, intlist = 20, [5, 4, 3, 7]
bestSum(target, intlist)
print(combinations, len(combinations))
现在所有与目标相加的组合都写入了组合，但这有一些问题..
以上代码打印 -
[[5, 5, 5, 5], [5, 5, 4, 3, 3], [5, 5, 3, 4, 3], [5, 5, 3, 3, 4], [5, 5, 3, 7], [5, 5, 7, 3], [5, 4, 5, 3, 3], [5, 4, 4, 4, 3], [5, 4, 4, 3, 4], [5, 4, 4, 7], [5, 4, 3, 5, 3], [5, 4, 3, 4, 4], [5, 4, 3, 3, 5], [5, 4, 7, 4], [5, 3, 5, 4, 3], [5, 3, 5, 3, 4], [5, 3, 5, 7], [5, 3, 4, 5, 3], [5, 3, 4, 4, 4], [5, 3, 4, 3, 5], [5, 3, 3, 5, 4], [5, 3, 3, 4, 5], [5, 3, 3, 3, 3, 3], [5, 3, 7, 5], [5, 7, 5, 3], [5, 7, 4, 4], [5, 7, 3, 5], [4, 5, 5, 3, 3], [4, 5, 4, 4, 3], [4, 5, 4, 3, 4], [4, 5, 4, 7], [4, 5, 3, 5, 3], [4, 5, 3, 4, 4], [4, 5, 3, 3, 5], [4, 5, 7, 4], [4, 4, 5, 4, 3], [4, 4, 5, 3, 4], [4, 4, 5, 7], [4, 4, 4, 5, 3], [4, 4, 4, 4, 4], [4, 4, 4, 3, 5], [4, 4, 3, 5, 4], [4, 4, 3, 4, 5], [4, 4, 3, 3, 3, 3], [4, 4, 7, 5], [4, 3, 5, 5, 3], [4, 3, 5, 4, 4], [4, 3, 5, 3, 5], [4, 3, 4, 5, 4], [4, 3, 4, 4, 5], [4, 3, 4, 3, 3, 3], [4, 3, 3, 5, 5], [4, 3, 3, 4, 3, 3], [4, 3, 3, 3, 4, 3], [4, 3, 3, 3, 3, 4], [4, 3, 3, 3, 7], [4, 3, 3, 7, 3], [4, 3, 7, 3, 3], [4, 7, 5, 4], [4, 7, 4, 5], [4, 7, 3, 3, 3], [3, 5, 5, 4, 3], [3, 5, 5, 3, 4], [3, 5, 5, 7], [3, 5, 4, 5, 3], [3, 5, 4, 4, 4], [3, 5, 4, 3, 5], [3, 5, 3, 5, 4], [3, 5, 3, 4, 5], [3, 5, 3, 3, 3, 3], [3, 5, 7, 5], [3, 4, 5, 5, 3], [3, 4, 5, 4, 4], [3, 4, 5, 3, 5], [3, 4, 4, 5, 4], [3, 4, 4, 4, 5], [3, 4, 4, 3, 3, 3], [3, 4, 3, 5, 5], [3, 4, 3, 4, 3, 3], [3, 4, 3, 3, 4, 3], [3, 4, 3, 3, 3, 4], [3, 4, 3, 3, 7], [3, 4, 3, 7, 3], [3, 4, 7, 3, 3], [3, 3, 5, 5, 4], [3, 3, 5, 4, 5], [3, 3, 5, 3, 3, 3], [3, 3, 4, 5, 5], [3, 3, 4, 4, 3, 3], [3, 3, 4, 3, 4, 3], [3, 3, 4, 3, 3, 4], [3, 3, 4, 3, 7], [3, 3, 4, 7, 3], [3, 3, 3, 5, 3, 3], [3, 3, 3, 4, 4, 3], [3, 3, 3, 4, 3, 4], [3, 3, 3, 4, 7], [3, 3, 3, 3, 5, 3], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5], [3, 3, 3, 7, 4], [3, 3, 7, 4, 3], [3, 3, 7, 3, 4], [3, 3, 7, 7], [3, 7, 5, 5], [3, 7, 4, 3, 3], [3, 7, 3, 4, 3], [3, 7, 3, 3, 4], [3, 7, 3, 7], [3, 7, 7, 3], [7, 5, 5, 3], [7, 5, 4, 4], [7, 5, 3, 5], [7, 4, 5, 4], [7, 4, 4, 5], [7, 4, 3, 3, 3], [7, 3, 5, 5], [7, 3, 4, 3, 3], [7, 3, 3, 4, 3], [7, 3, 3, 3, 4], [7, 3, 3, 7], [7, 3, 7, 3], [7, 7, 3, 3]] 123
仅仅为了 20 的一个小目标，就有多达 123 种组合。如果您浏览组合列表，您会注意到 combinations 包括给定有效组合的所有排列，从而导致这种臃肿的大小。该代码还必须做额外的工作来导出所有这些组合。
我们可以做些什么来避免这些重复？
排序来拯救;如果我们确保每个有效组合始终排序，则最终 combinations 中不能有相同组合的排列。如何在代码中利用这一点？
combinations = []
def bestSum(target, intlist, combination=[]):
if (target == 0):
# found a valid combination
combinations.append(combination)
return
if (target < 0):
return
for i in intlist[::-1]:
# each combination will be in ascending order
# while i is in descending order here, so if last element in my
# combination is greater than i, we can break the loop to stop
# additional work, and make sure that all the combinations are unique
if combination and combination[-1] > i:
break
remainder = target - i
bestSum(remainder, intlist, combination + [i])
target, intlist = 20, [5, 4, 3, 7]
bestSum(target, sorted(intlist)) # sort list of values
print(combinations, len(combinations))
这个输出
[[5, 5, 5, 5], [4, 4, 5, 7], [4, 4, 4, 4, 4], [3, 5, 5, 7], [3, 4, 4, 4, 5], [3, 3, 7, 7], [3, 3, 4, 5, 5], [3, 3, 3, 4, 7], [3, 3, 3, 3, 4, 4], [3, 3, 3, 3, 3, 5]] 10
现在，我们的组合中没有任何排列！我们可以很容易地从 combinations.
但是正如@karl 在他的回答中所指出的，这个接口看起来很糟糕，我们实际上应该使用递归生成器来使接口更清晰。看起来像这样 -
def bestSum(target, intlist, combination=[]):
if (target == 0):
# found a valid combination
yield combination
if (target < 0):
return
for i in intlist[::-1]:
if combination and combination[-1] > i:
break
remainder = target - i
yield from bestSum(remainder, intlist, combination + [i])
target, intlist = 20, [5, 4, 3, 7]
intlist.sort()
targetCombinations = list(bestSum(target, intlist))
targetCombinations.sort(key=lambda x: len(x))
print("One of the shortest combination - ", targetCombinations[0])
使用递归仅返回最短路径之一 - 仅使用 return 和使用单个递归函数是不可能的，因为一旦我们 return 一个值，我们将无法继续搜索剩余的组合。因此，解决此问题的一种方法是将递归函数包装在另一个函数中，并使 return 成为您在完成所有组合后遇到的最短组合或使用全局变量（我会避免采用全局变量方式) 或通过引用原始函数传递变量。
def shortestCombinationSum(target, intlist, combination=[]):
shortest = None
def bestSum(target, intlist, combination):
nonlocal shortest
if (target == 0 and (not shortest or len(combination) < len(shortest))):
# found a valid combination which is shorter
shortest = combination
return
if (target < 0):
return
for i in intlist[::-1]:
if combination and combination[-1] > i:
break
remainder = target - i
bestSum(remainder, intlist, combination + [i])
bestSum(target, intlist, combination)
return shortest
target, intlist = 20, [5, 4, 3, 7]
print(shortestCombinationSum(target, sorted(intlist)))
虽然这使函数看起来很奇怪，但 shortestCombinationSum 的界面相当干净。另一种选择可能是将 shortest 作为全局变量然后不断更新它，在这种情况下我们不必将函数包装在另一个函数中，但我们必须清除全局变量的值如果我们用不同的输入集一遍又一遍地调用函数。
我仍然会推荐迭代解决方案而不是上面的递归解决方案，因为给定大小 n 的 intlist，您在图表中的树将是 n-ary tree，具有每个节点上的 n 个分支从顶部的 target 开始。迭代解类似于 n 叉树中的层次顺序遍历，当它到达找到解的层次时将停止。虽然递归解决方案是树上的 DFS，但它需要遍历 n 叉树的每个组合（修剪重复排列）。
这是一个简单的：
import itertools as it
# create all possible route
def create_permutation(data):
final = []
for k in range(1, len(data) + 1):
temp = list(it.permutations(data, k))
final.extend(temp)
return final
# find best sum in equal to num
def best_sum(subs, num, _min = True):
final = []
for i in range(len(subs)):
temp_sums = sum(subs[i])
if temp_sums == num:
final.append(subs[i])
if not final:
return None
# if only wants minimum then sort by length then return first
if _min:
return sorted(final, key = lambda x : len(x))[0]
return final
def main(data, num):
subs = create_permutation(data)
result = best_sum(subs, num, False)
print("Best === ", result)
data = [5, 3, 4, 7, 2]
num = 7
main(data, num)