代码随想训练营第二十四天（Python）

第77题. 组合
需要注意剪枝细节
纵向代表递归，横行代表取数
1、回溯

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        self.backtrack(n, k, 1, [], res)
        return res

    def backtrack(self, n, k, start, path, res):
        if len(path) == k:
            res.append(path[:])
            return

        for i in range(start, n+1):   # 代表取数
            path.append(i)
            self.backtrack(n, k, i+1, path, res)
            path.pop()

2、回溯优化

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        self.backtrack(n, k, 1, [], res)
        return res

    def backtrack(self, n, k, start, path, res):
        if len(path) == k:
            res.append(path[:])
            return

        for i in range(start, n-(k-len(path))+2):
            path.append(i)
            self.backtrack(n, k, i+1, path, res)
            path.pop()