回溯算法：递归函数里面嵌套着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.resultdef 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=9k=3s=solution()print(s.combine(n,k，1))