我试图理解以下程序，以从给定列表中查找形成给定总和的子集的数量。
def count_sets(arr, total):
return rec(arr, total, len(arr)-1)
def rec(arr, total, i):
print(arr, total, i)
if total == 0:
return 1
if i < 0:
return 0
if arr[i] > total:
return rec(arr, total, i-1)
else:
return rec(arr, total-arr[i], i-1) + rec(arr, total, i-1)
arr = [2,10,6,4]
print(count_sets(arr, 16))
该程序可以正常工作，但是我无法找到它的工作方式。
最佳答案
这是一个backtracking算法。在recursion rec(arr, total, i)中，它选择rest数组中的最后一个元素arr[i]，这是两种主要情况：
使用arr[i]：rec(arr, total-arr[i], i-1)
不要使用arr[i]：rec(arr, total, i-1)，并且当arr[i] > total当然不能使用时。
并且必须具有recursion的终止条件，即：
[成功]找到等于总数的子数组：if total == 0: return 1
[失败]到达头部：if i < 0: return 0
希望我能说清楚，如果您还有其他问题，请发表评论。 :)
关于python - Python理解递归程序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55652642/