刷题笔记day27-回溯算法1

理论基础

77. 组合

class Solution:
    path: list = list()
    result: List[List[int]] = list()
    def traversal(self, left: int, n: int, k: int):
        # 终止条件
        if (len(self.path) == k):
            # 这里面需要用浅拷贝，而不能是引用
            self.result.append(copy.copy(self.path))
            # print(self.path)
            return 
        
        # 2、迭代所有
        for i in range(left, n+1):
            self.path.append(i)
            self.traversal(i+1, n, k)
            del self.path[-1]
        
        return 


    def combine(self, n: int, k: int) -> List[List[int]]:
        # 先清空，避免多轮测试
        self.path.clear()
        self.result.clear()
        self.traversal(1, n, k)
        return self.result
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26