我有以下问题的解决方案：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'在主函数中是否正确？
组合的（副本）在递归curr的最深 层次输出（嗯，它应该是最深的，目前代码继续循环，即使事先知道它是徒劳的，即没有机会产生任何输出，即当的长度curr是大于比k）。
这种组合是建立在方式上的，一次一个元素。
添加元素，进入递归（最终达到最深层次，将组合的副本收集到输出中），然后递归展开，最终退出递归调用 --- 所以我们必须删除元素我们已经投入了，所以我们可以把下一个元素进入curr，对下一个迭代是的for ... 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()
直接改变jth值也可以达到同样的效果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”的全部含义。只是广义的嵌套循环，协同工作以从最深的内部产生输出，无论它上面有多少层。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句