回溯算法：递归函数里面嵌套着for循环

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。
示例: 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

包含组合问题和组合问题的剪枝优化

class solution:
     def combine(self,n,k,startindex):
         self.path=[]
         self.result=[]
         self.backtracking(n,k,startindex)
         
         return self.result


     def backtracking(self,n:int,k:int,startindex:int):
        # 递归的终止条件
        if len(self.path)==k:
            self.result.append(self.path[:]) # 结果拷贝

            return self.result

        # for i in range(startindex,n+1):# 横向处理，在没有剪枝的情况下需要遍历 数组的长度 次
        #     # 单层递归的逻辑：二叉树深度搜索
        #     self.path.append(i)
        #     self.backtracking(n,k,i+1)
        #     self.path.pop()

        # 剪枝优化
        for i in range(startindex, n-(k-len(self.path)) + 2):
            # 剪枝处理，i再大，就不满足k个了，就搜不到对应的组合了
            # 单层递归的逻辑：二叉树深度搜索
            self.path.append(i)
            self.backtracking(n, k, i + 1)
            self.path.pop() #回溯处理

if __name__ == '__main__':
    n=9
    k=3
    s=solution()
    print(s.combine(n,k，1))