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

Question

我正在尝试编写一个程序作为输入：

1. 允许的号码列表（arr）
2. 共（sum）

它应该返回所有数字的可能组合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

在每次递归时，我为 中的每个数字创建一个新分支arr。我保留了总和与目标匹配的分支，并停止探索总和超过目标的分支。

更快（将分支的累积和沿着调用链传递）

def array_sums(arr: Set[int], target: int) -> List[List[int]]:
    smallest = min(arr)

    def go(
            in_progress: List[Tuple[List[int], int]],
            complete: List[List[int]]
    ) -> List[List[int]]:

        now_in_progress, newly_complete = [], []
        for branch, sum_ in in_progress:
            for i in arr:
                # anything short of `target` by less than `smallest` will overshoot
                if sum_ + i <= target - smallest:
                    now_in_progress.append((branch + [i], sum_ + i))
                elif sum_ + i == target:
                    newly_complete.append(branch + [i])

        newly_complete += complete

        return newly_complete if not now_in_progress else go(
            now_in_progress, newly_complete
        )

    return go([([], 0)], [])

更简单且纯函数式（计算每次递归时分支的总和）

def array_sums(arr: Set[int], target: int) -> List[List[int]]:
    def go(acc: List[List[int]]) -> List[List[int]]:
        in_progress = [
            branch + [i]
            for branch in acc
            for i in arr
            if sum(branch) < target
        ]

        complete = [branch for branch in acc if sum(branch) == target]

        return complete if not in_progress else go(in_progress + complete)

    return go([[]])