递归回溯以列出所有具有给定和的子集？

Question

我试图打印出所有可能的子数组，这些子数组的总和是给定的目标数。你知道吗

# arr -- the array
# n -- length of the array
# target_sum -- sum we want
# target_arr -- subarray we test for having the right sum
# ite -- iterator

def subset_sum(arr,n,target_sum,target_arr=[],ite=0):
    for i in range(ite,n):
        target_arr.append(arr[i])
        if sum(target_arr)==target_sum:
            print (target_arr, len(target_arr))
            target_arr.pop()
            subset_sum(arr,n,target_sum,target_arr,ite+1)
            return
        subset_sum(arr,n,target_sum,target_arr,i+1)
        target_arr.pop()

subset_sum([1,2,3,4],4,4)
[1, 3] 2
[1, 3] 2
[4] 1
[4] 1
[4] 1
[4] 1.

我似乎可以打印所有的子数组，但我不知道为什么我的代码要我打印副本。我以为可以避免重复，因为我在最后弹出了我的子阵列（即回溯）。你知道吗

我的代码在哪里导致了重复？我试过了，但不知道为什么。你知道吗

Answer 1

Where in my code is causing repeats?

我将重新排列您的代码：它将返回结果，而不是打印结果；它将重新排列参数，这样target_array就不需要被传递；它将使用一个更简单的带有重复项的示例输入：

def subset_sum(array, target_sum, start=0, target_array=[]):  # dangerous default value
    solutions = []

    for idx in range(start, len(array)):
        target_array.append(array[idx])

        if sum(target_array) == target_sum:
            solutions.append(list(target_array))
            target_array.pop()
            solutions.extend(subset_sum(array, target_sum, start + 1))
            break

        solutions.extend(subset_sum(array, target_sum, idx + 1))

        target_array.pop()

    return solutions

print(*subset_sum([1, 2, 3], 4))

但它仍然存在相同的重复问题：

> python3 test.py
[1, 3] [1, 3]
>

现在，我将添加一个调试print语句：

        target_array.pop()
        print(f"print(*subset_sum({array}, {target_sum}, {start}, {target_array}))")
        solutions.extend(subset_sum(array, target_sum, start + 1))

现在当我们运行它时，我们得到：

> python3 test.py
print(*subset_sum([1, 2, 3], 4, 1, [1]))
print(*subset_sum([1, 2, 3], 4, 2, [1]))
[1, 3] [1, 3]
>

我们可以用上面的两个调用替换原来的调用来确认这两个调用都产生相同的输出。通过更多基于print的搜索，我们可以确定第一个是内环递归调用的结果，第二个是外环递归调用的结果。调用（参数）中没有重复，但是两个不同的调用产生相同的结果。你知道吗

您可以拔出头发来尝试解决这个问题，或者简单地将solutions切换为set而不是list，然后让Python过滤掉原始示例调用中的重复项：

def subset_sum(array, target_sum, start=0, target_array=[]):  # dangerous default value
    solutions = set()

    for idx in range(start, len(array)):
        target_array.append(array[idx])

        if sum(target_array) == target_sum:
            solutions.add(tuple(target_array))
            target_array.pop()
            solutions |= subset_sum(array, target_sum, start + 1)
            break

        solutions |= subset_sum(array, target_sum, idx + 1)

        target_array.pop()

    return solutions

print(*subset_sum([1, 2, 3, 4], 4))

带输出：

> python3 test.py
(1, 3) (4,)
>