python - 获取具有给定总和的所有子集的递归程序包括重复

Question

我正在尝试编写一个接受输入的程序:

1. 允许的数字列表 (arr)
2. 总计(总和)

它应该返回 arr 中加起来为 sum 的所有可能的数字组合。

这是我目前所拥有的:

def printAllSubsetsRec(arr, v, sum):
    if sum == 0:
        return [v]

    if len(arr) == 0:
        return

    v1 = [] + v
    v1.append(arr[0])
    without_first = printAllSubsetsRec(arr[1:], v, sum)
    with_first = printAllSubsetsRec(arr[1:], v1, sum - arr[0])
    if with_first and without_first:
        return with_first + without_first

    elif with_first:
        return with_first
    elif without_first:
        return without_first

def array_sums(arr, sum):
    v = []
    return printAllSubsetsRec(arr, v, sum)

问题是它没有返回所有子集，包括重复。

例如:

print(array_sums([1,3,5],5))
# [[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [3, 1, 1], [5]]

我该怎么做？

Answer 1

您可以将递归与生成器一起使用:

def subsets(arr, _sum, c = []):
  if sum(c) == _sum:
    yield c
  else:
    for i in arr:
      if sum(c+[i]) <= _sum:
         yield from subsets(arr, _sum, c+[i])

print(list(subsets([1,3,5], 5)))

输出:

[[1, 1, 1, 1, 1], [1, 1, 3], [1, 3, 1], [3, 1, 1], [5]]