一个函数，它返回所有可能的子数组，这些子数组的总和为特定的给定数字(不必是连续的子数组)

Question

当我做一些数学运算时，我遇到了这个问题，我需要找到给定数字的所有可能的总和。下面是一个示例输入和输出，用于更好地了解问题。 假设我们得到了一个数组arr=[1,2,3,4,5]和给定的数字number=10那么我需要这样的东西，

def solution(arr,number):
#you can code here

输出 ：[1,2,3,4],[2,3,5],[1,5,4],[1,3,6],[1,6]

Answer 1

这里和这里都有很多有趣的答案和讨论。

以下是为您提供的快速(经过测试的(答案：

import itertools
def solution(arr, number):
for i in range(len(arr)+1):
for s in list(itertools.combinations(arr, i)):
if sum(s) == number:
yield list(s)

arr = [ 1, 2, 3, 4, 5 ]
number = 10
print(list(solution(arr, number)))

指纹：

[[1, 4, 5], [2, 3, 5], [1, 2, 3, 4]]

Answer 2

使用动态规划算法求解

def solve(arr, s, i = None, path = None, solutions = None):
"""Use Dynamic Programming to find subsequence of arr
that sum to s

Arguments:
arr      - array
i        - current index that will use or not for arr
path     - current subsequence we are summing
solutions - all solutions found
"""
# Set defaults
if i is None:
i = len(arr) - 1
if solutions is None:
solutions = []
if path is None:
path = []
# Base Cases
if s == 0:
solutions.append(path[:])
return solutions
if i < 0 or s < 0:
return
# Try with arr[i] in path
if arr[i] <= s:
solve(arr, s-arr[i], i-1, [arr[i]] + path, solutions)
# Try with arr[i] not in path
solve(arr, s, i-1, path, solutions)
return solutions

测试

arr = [1, 2, 3, 4, 5]
print(solve(arr, 10))

输出

[[1, 4, 5], [2, 3, 5], [1, 2, 3, 4]]