【代码随想录|回溯算法 77. 组合】

代码随想录|回溯算法 77. 组合，216.组合总和 III，17.电话号码的字母组合

• 一、77. 组合
• • 1.核心代码
  • 2.输入输出
  • 3.问题
• 总结

python

一、77. 组合

内容
77. 组合

1.核心代码

代码如下（示例）：

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []  # 存放结果集
        self.backtracking(n, k, 1, [], result)
        return result
    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startIndex, n - (k - len(path)) + 2):  # 优化的地方
            path.append(i)  # 处理节点
            self.backtracking(n, k, i + 1, path, result)
            path.pop()  # 回溯，撤销处理的节点

result.append(path[:])是浅拷贝。否则，因为通过append把path添加到result，是引用对象，所以后续path改变，result也会改变。而增加了[:]后，后续修改不会影响前面的引用了

2.输入输出

class Solution:
    def combine(self,n,k):
        result = []
        self.backtracking(n,k,1,[],result)
        return result
    def backtracking(self,n,k,startIndex,path,result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startIndex, n-(k-len(path))+2):
            path.append(i)
            self.backtracking(n,k,i+1,path,result)
            path.pop()

if __name__=="__main__":
    n=int(input())
    k=int(input())
    solution=Solution()
    result=solution.combine(n,k)
    print(result)

3.问题

combine 方法调用了 backtraversal 方法，而 backtraversal 方法是定义在类内的，因此需要通过 self 进行调用。
backtraversal 方法的签名中缺少 self。没有 self 的话，方法无法正确绑定到实例上，也无法访问实例变量和方法。

总结

输入输出