题目：
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
提示：
1 <= n <= 201 <= k <= n
思路（path[:]的作用）：
本题是回溯法的经典题目。
可以直接套用模板（需要理解具体题目含义，此处就不做详细分析），模板如下：
def backtracking(self, 参数):
if (终止条件):
存放结果
return
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小)
处理节点
self.backtracking(路径，选择列表) # 递归
回溯，撤销处理结果这里需要注意下本题中 result.append(path[:]) （见下图完整代码）， 为什么不是result.append(path)呢？
在这里，path[:]的作用是创建path列表的副本。当我们使用path[:]时，实际上是对path列表进行了浅拷贝，得到了一个新的列表，该列表与path具有相同的元素。这样做的目的是为了避免直接操作原始的path列表，因为在回溯算法中，我们会频繁地对path进行添加和删除操作，如果直接操作原始的path列表，会导致结果不准确。通过使用path[:]创建副本，我们可以在不影响原始path列表的情况下，将其添加到result列表中，确保每个结果都是正确的。
剪枝优化：
回溯法虽然是暴力搜索，但也有时候可以有点剪枝优化一下的。
来举一个例子，n = 4，k = 4的话，那么第一层for循环的时候，从元素2开始的遍历都没有意义了。 在第二层for循环，从元素3开始的遍历都没有意义了。
图中每一个节点（图中为矩形），就代表本层的一个for循环，那么每一层的for循环从第二个数开始遍历的话，都没有意义，都是无效遍历。
所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
优化前代码：
for i in range(startIndex, n + 1): 优化过程如下
-
已经选择的元素个数：len(path)
-
还需要的元素个数为: k - len(path)
-
在集合n中至多要从该起始位置 : n - (k - len(path)) + 2，开始遍历
为什么是+2呢，因为左闭右开，i最多为n - (k - len(path)) + 1
举个例子，n = 4，k = 3， 目前已经选取的元素为0（len(path)为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。
从2开始搜索都是合理的，可以是组合[2, 3, 4]。
优化后代码：
for i in range(startIndex, n - (k - len(path)) + 2):
代码：
未剪枝：
from typing import List
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: # 如果当前组合的长度达到要求的k
result.append(path[:]) # 将当前组合加入最终结果列表
return result # 返回最终结果列表
for i in range(startIndex, n + 1): # 遍历所有可能的元素 未剪枝 可以进行优化
path.append(i) # 将当前元素加入组合
self.backtracking(n, k, i + 1, path, result) # 递归调用回溯函数，startIndex更新为i+1
path.pop() # 回溯，将当前元素从组合中移除
剪枝优化:
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 result
for i in range(startIndex, n - (k - len(path)) + 2): # 优化地方
path.append(i)
self.backtracking(n, k, i + 1, path, result)
path.pop()
