我正在尝试使用DFS实现"子集"算法。我发现以下两个程序都起作用：
def DFS(nums, begin, path, res):
res.append(path[:])
for i in range(begin, len(nums)):
path.append(nums[i])
DFS(nums, i + 1, path, res)
path.pop()
def DFS_2(nums, begin, path, res):
if begin == len(nums):
res.append(path[:])
return
path.append(nums[begin])
DFS_2(nums, begin + 1, path, res) #choose the current element
path.pop()
DFS_2(nums, begin + 1, path, res) #not choose the current element
测试代码是：
nums = [i for i in range(1, 4)]
res = []
path = []
DFS_2(nums, 0, path, res)
print(res)
res2 = []
DFS(nums, 0, path, res2)
print(res2)
输出是：
dfs_2： [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
dfs： [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
我可以理解DFS_2，因为在每次递归中，我都有两个选择 - 选择当前元素或不选择当前元素。但是我很难理解功能DFS。如何了解该功能DFS中的for循环？我的猜测是功能DFS_2中有尾部递归，这就是函数DFS和DFS_2彼此等效的原因，但我不确定细节。
任何提示都将被赞赏。
好吧，功能 dfs 和 dfs_2 几乎相互等效。是的，您在函数 dfs_2 中有两个选择，而且确实很容易看到，但是函数 dfs 中也有两个选择。当程序在 path 列表中附加元素时，它是对该路径进行递归的递归，但是当递归的 branch 递归结束时，消除了相同的元素从路径开始，然后开始与以前相同的递归，但是在路径列表中没有该元素。
如果您打印 path 列表> dfs 函数后，输出将为：
（'附录后路径：'，[1]）
（'附录后路径：'，[1，2]）
（'附录后路径：'，[1，2，3]）
（'附录后路径：'，[1，3]）
（'附录后路径：'，[2]）
（'附录后路径：'，[2，3]）
（'附录后路径：'，[3]）
让我们看看，递归始于第一个元素，并进行了所有可能的排列。之后，进行了相同的递归，但没有第一个元素，依此类推，列表中的所有元素都做了同样的事情。总而言之， i th 元素的每个递归本身都会看到所有元素，并执行所有可能的排列。在开始的第一个元素列表中，然后将递归放在列表中，然后放置第二个元素，然后将第三个元素放在第三个元素中，然后递归介绍，删除第三个元素，然后再添加第三个元素，然后再添加第三个元素，但那里没有第二个元素。然后删除第二个元素，并为第一个元素完成所有排列。所有这些都发生了同样的事情，但是正如我所说， i 的每个递归列表中的元素本身仅在本身上看到所有元素。