为什么我们在每次回溯迭代结束时从列表中弹出？

Question

我有以下问题的解决方案：https://leetcode.com/problems/combinations/

List[List[int]]:
        def backtrack(first = 1, curr = []):
            # if the combination is done
            if len(curr) == k:  
                output.append(curr[:])
            for i in range(first, n + 1):
                # add i into the current combination
                curr.append(i)
                # use next integers to complete the combination
                backtrack(i + 1, curr)
                # backtrack
                curr.pop()
        
        output = []
        backtrack()
        return output

我的问题是 curr.pop() 为什么我们每次迭代都会弹出 curr 组合？不应该有一些条件，比如如果 curr 已经在输出中了吗？

另一个问题是递归调用 backtrack(i+1, curr) - 当它被调用时，我说的'i+1' 取代了 main 中的'first' 是对的吗功能？

Answer 1

组合 curr 的（副本）在递归的 deepest level 输出（好吧，它应该是最深的，目前代码继续循环，即使事先知道它是徒劳的，即没有机会产生任何输出，即当 curr 的长度大于比 k).

组合建立在插入的方式上，一次一个元素。

添加元素，进入递归（最终达到最深层次，组合的副本被收集到输出中）然后递归展开，最终退出递归调用---所以我们必须删除我们已经放入的元素，这样我们就可以在 的下一次迭代 中将 next 元素放入 curr 17=]循环（应该由if len(curr) < k: ....保护）。

所以是的，i+1 是 “新” first 的值——在 下一步 for ... range ...循环，更深一层。因此，这里发生的事情是递归实际上构建了嵌套循环结构，其中最深的循环具有 curr 完全设置和填充，因此将其添加到 output.

或伪代码：

for i1 in range( 1, n+1): for i2 in range( i1+1, n+1): ......... for ik in range( ik1+1, n+1): output.append( [i1,i2,...,ik1,ik] )

（除了你的代码效率低下，它不断为 k+1、k+2、...、n 级别创建更多循环，即使我们已经知道这一切都是徒劳的，因为我们只需要长度的组合 k).

这是它的要点，尽管您的代码没有在最深层次构建 curr，如上所示，而是通过附加 i<sub>j </sub> 每个（j）级别。这就是为什么在 for 循环中附加下一个值之前它需要 pop 它，实际上更新 j 中的第 [=13] 个位置=]:

for i1 in range( 1, n+1): curr.append(i1) for i2 in range( i1+1, n+1): curr.append(i2) ......... for ik in range( ik1+1, n+1): curr.append(ik) output.append( curr ) curr.pop() ......... curr.pop() curr.pop()

直接改变curr中的第j个值也可以达到同样的效果。您需要为此预先创建 k-long curr（最初填充一些不重要的值），并为此引入一个额外的计数器：

for i1 in range( 1, n+1): curr[0] = i1 # j == 0 for i2 in range( i1+1, n+1): curr[1] = i2 # j == 1 ......... for ik in range( ik1+1, n+1): curr[k-1] = ik # j == k-1 output.append( curr )

这就是 （按时间顺序）回溯 的全部内容。只是 嵌套循环 ，每个循环都保持其状态，准备在控件 returns（回溯）到它时尝试另一个替代方案。

此外，这就是 "monads" 的意义所在。只是广义嵌套循环，协同工作以从最深内部产生输出，不管上面有多少层

为什么我们在每次回溯迭代结束时从列表中弹出？

Why do we pop from the list at the end of each backtrack iteration?

python

recursion

recursive-backtracking