时间戳

首页 > 解决方案 > 为什么我们在每次回溯迭代结束时从列表中弹出？

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

问题描述

我有以下问题的解决方案：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每次迭代都会弹出组合？不应该有一些条件，比如 ifcurr已经在输出中吗？

另一个问题是递归调用backtrack(i+1, curr)- 当调用它时，我是否正确地说 ' i+1' 代替first了 main 函数中的 ' '？

标签： pythonrecursionrecursive-backtracking

解决方案

组合的（副本）以最深的递归级别curr输出（嗯，它应该是最深的，当前代码继续循环，即使事先知道它是徒劳的，即没有机会产生任何输出，即当的长度大于) 。 currk

这种组合是在进入的过程中构建的，一次一个元素。

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

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

或者在伪代码中：

   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级别创建更多循环，即使我们已经知道这一切都是徒劳的，因为我们只需要 length 的组合k）。

这是它的要点，尽管您的代码不会curr在最深层次构建 while，如上所示，而是通过在每个 ( th) 级别附加。这就是为什么它在从循环中附加下一个值之前需要它，实际上更新了th 中的位置：ijjpopforjcurr

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

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

   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 )

这就是（按时间顺序）回溯的全部内容。只是嵌套循环，每个循环都保持其状态，准备好在控件返回（回溯）时尝试另一种选择。

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

推荐阅读