2023-08-02

组合回溯

image.png

class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []

    self.backtrack(n,k,1,[],result)

    return result

def backtrack(self,n,k,startindex, path,result):

    if len(path) == k:
        result.append(path[:])
        return

    for i in range(startindex,n+1):
        
        print("i = {}, startIndex = {},n+1 = {}".format(i , startindex,n +1))
        print(" before append -- - path = {}".format(path))
     
        path.append(i)

        print(" after append - path = {}".format(path))

        print ("i + 1 = {}".format(i +1))
     
        self.backtrack(n,k,i+1,path,result)
        path.pop()

self.backtrack(n,k,i+1,path,result) 参数k+1 是下一层递归起始位置
你可以理解都在一层发生的，pathadd(1) 这个操作结束后，递归下去然后回来到这一层， 再把1pop出来，接着i++，开始i=2，重复刚才的步骤

就是如果path长度够以后，从13行的return返回到上一层的24行，上一层就会接着执行pop的操作回溯，i++选择其他的元素继续刚才的步骤

[1,4] 结果在13行 收集以后 跳回第二层24行 然后25行pop(4)出来 这时候数组是[1] 而且i = 4 循环走完了 跳回到第一层的24行 走到25行pop(1) 变成[]

怎么实现把 path = [1,4] 变成 []
好像想明白了，这是在一个for循环中的递归 ，所以递归完了之后，然后继续把这个 for循环最后一步走完 。之前是一直递归没有走完，现在相当于递归完了，继续这个for循环中的递归后面那个 pop方法
这就是为什么直接走到最后那一步pop的原因