回溯总结

经典格式：

例如78题

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        for i in range(len(nums)+1):  #len+1轮循环，每次输出长度为i的所有组合
            self.backtrack(nums, tmpList, i, 0)
        return self.res

    def backtrack(self, nums, tmpList, k, start):
        if len(tmpList) == k:
            self.res.append(list(tmpList))
        else:
            for i in range(start, len(nums)):
                #经典回溯格式
                tmpList.append(nums[i])
                self.backtrack(nums, tmpList, k, i + 1)
                tmpList.pop()

简化

上面的递归操作实质上是将本层tmpList修改后传入下一层递归，待递归完成后再将tmpList还原。这波操作可以简化为直接在下一层递归函数的参数中对tmpList修改，这样本层递归的tmpList其实是不变的，即不能对tmpList做直接操作。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        tmpList = []
        for i in range(len(nums)+1):  #len+1轮循环，每次输出长度为i的所有组合
            self.backtrack(nums, tmpList, i, 0)
        return self.res

    def backtrack(self, nums, tmpList, k, start):
        if len(tmpList) == k:
            self.res.append(list(tmpList))
        else:
            for i in range(start, len(nums)):    
                #tmp的修改直接写在递归里
                self.backtrack(nums, tmpList+[nums[i]], k, i + 1)

例如，若15行写作

self.backtrack(nums, tmpList.append([nums[i]]), k, i + 1)

则报错，因为调用append函数对tmpList本身做了修改操作。回溯时本层的tmpList无法回复之前的状态

再简化

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        self.res = []
        # 方法内定义回溯
        def backtrack(tmp, start, k):
            if len(tmp) == k:
                self.res.append(list(tmp))
            for i in range(start, len(nums)):
                backtrack(tmp+[nums[i]], i+1, k)
        
        for i in range(len(nums)+1):
            backtrack([], 0, i)  #递归
        return self.res

题目列表：

22.括号生成

36.有效的数独

37.解数独

39.组合总和

40.组合总和Ⅱ

46.全排列

47.全排列Ⅱ

77.组合

78.子集

90.子集Ⅱ