力扣：77. 组合（回溯， path[:]的作用）

题目：

给定两个整数?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 <= 20
• 1 <= 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):?

?优化过程如下

1. 已经选择的元素个数：len(path)

2. 还需要的元素个数为: k - len(path)

3. 在集合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()