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

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

我的代码中哪里导致重复？

我将稍微重新排列你的代码：它将返回结果而不是打印它们;它将重新排列其参数，以便不需要传递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]
>

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

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,)
>