How to check recursively if I can create a sum from a list or from a sublist of numbers?
[23, 40, 20, 6, 3, 12, 20, 21, 18, 17]
I can create 64 from the list [40,6,18], but I can't create 34 from any sublist.
问问题
774 次
2 回答
2
要确定是否可以从数字列表或子列表创建总和：
1) 从第一个数字开始。
2）如果该数字等于您尝试创建的总和，请停止，您已经成功。
3) 如果该数字大于您尝试创建的总和，请跳至下一个数字并转到第 2 步。
4）从您要查找的总和中减去该数字。
5）重复这个算法，尝试用剩余的数字（在这个数字之后的那些）找到剩余的总和。
6) 转到下一个号码。如果没有，请停止。
7) 转到步骤 2。
因此，例如，如果您尝试从 [1, 13, 17, 8] 中找到 55 的总和，您可以将其简化为以下三个问题：
你能从 [13, 17, 8] 中找到 55-1 的总和吗？（这将找到包含第一个数字的任何解决方案。）
你能从 [17, 8] 中找到 55-13 的总和吗？（这将找到不包含第一个数字但包含第二个数字的任何解决方案。）
你能从 [8] 中找到 55-17 的总和吗？（这将找到任何不包含第一个或第二个数字但包含第三个数字的解决方案。）
8是解决方案吗？（这将找到不包含前三个数字但包含第四个数字的任何解决方案。）
请注意，每个新问题的术语都比原始问题少。所以它不会永远持续下去。
于 2013-01-18T14:13:48.770 回答
1
如果这是家庭作业，那么提供一个非递归的解决方案对您没有帮助。如果它不是家庭作业，那么不要强迫自己使用递归......改用 itertools ：
>>> lst =[23, 40, 20, 6, 3, 12, 20, 21, 18, 17]
>>> from itertools import chain,combinations
>>>
>>> def powerset(iterable):
... "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
... s = list(iterable)
... return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))
...
>>> next(x for x in powerset(lst) if sum(x) == 64)
(23, 20, 21)
于 2013-01-18T14:15:15.320 回答