第72课：全排列与组合

学习目标

完成本课学习后，你将能够：

1. 理解并实现生成一个序列全排列（Permutation）的回溯算法。
2. 理解并实现在 n 个元素中选择 k 个元素的组合（Combination）的回溯算法。
3. 掌握使用递归与回溯框架解决排列组合类问题的核心模式。
4. 学会区分排列（顺序重要）与组合（顺序不重要）问题的本质差异，并能应用相应的解法。
5. 能够解决涉及子集生成、组合总和等常见的排列组合变种问题。

核心概念

1. 全排列 (Permutation)

通俗理解：想象你有三个不同颜色的球（A, B, C）。把它们排成一排，列出所有可能的排列顺序。这就是全排列。特点是顺序非常重要，AB 和 BA 是两种不同的结果。

• 对于一个包含 n 个不同元素的列表，其全排列共有 n! 种。
• 生成全排列的经典思路：回溯法。我们尝试将每个位置，依次填入一个未使用的元素，填完一个位置后，再递归地去填下一个位置。当所有位置都填好，我们就找到了一个排列。之后，我们需要“撤销”最后一步操作（回溯），尝试其他可能性。

2. 组合 (Combination)

通俗理解：继续用三个球的例子。如果从这三个球中选出两个，不考虑顺序，那么选到A和B（即集合{A,B}）就算一种组合，至于你先拿A还是先拿B，都算作同一种选择。特点是顺序不重要。

• 对于 n 个不同元素，从中选出 k 个元素的组合数，通常用 C(n, k) 表示。
• 生成组合的回溯思路与排列类似，但有一个关键区别：为了避免重复（如选出{A,B}和{B,A}），我们在选择下一个元素时，通常只考虑当前元素之后的元素（需要一个起始索引 start）。

3. 子集 (Subset)

子集问题是组合问题的一个特例，即从 n 个元素中选出 所有可能的 k（从0到n）个元素的情况。它本质上是生成所有长度的组合。我们同样可以使用带有 start 参数的回溯来生成。

代码示例

示例1：生成全排列 (Permutations)

def permutations(nums):
    """
    生成一个列表的全排列。
    :param nums: 不含重复数字的列表
    :return: 所有排列的列表
    """
    result = []
    path = []  # 用于记录当前路径（当前排列）
    used = [False] * len(nums)  # 用于记录哪些数字已经被使用

    def backtrack():
        # 终止条件：路径长度等于列表长度，说明找到一个完整排列
        if len(path) == len(nums):
            result.append(path[:])  # 注意要拷贝一份加入结果
            return

        for i in range(len(nums)):
            if not used[i]:  # 如果这个数字还没被用过
                used[i] = True
                path.append(nums[i])
                backtrack()  # 递归去填下一个位置
                # 回溯：撤销选择，尝试其他数字
                path.pop()
                used[i] = False

    backtrack()
    return result

# 测试
nums = [1, 2, 3]
print(f"输入: {nums}")
print("全排列:")
perm_result = permutations(nums)
for p in perm_result:
    print(p)

输出：

输入: [1, 2, 3]
全排列:
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

示例2：生成组合 (Combinations)

def combinations(n, k):
    """
    生成从1到n的数字中，选择k个数字的所有组合。
    :param n: 数字范围1..n
    :param k: 选择的个数
    :return: 所有组合的列表
    """
    result = []
    path = []

    def backtrack(start):
        # 终止条件：路径长度达到k
        if len(path) == k:
            result.append(path[:])
            return

        # 从start开始，避免重复和顺序问题
        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1)  # 从下一个数字开始选，保证不重复选择同一个数字
            path.pop()  # 回溯

    backtrack(1)
    return result

# 测试
n, k = 4, 2
print(f"从1到{n}中选{k}个数的组合:")
comb_result = combinations(n, k)
for c in comb_result:
    print(c)

输出：

从1到4中选2个数的组合:
[1, 2]
[1, 3]
[1, 4]
[2, 3]
[2, 4]
[3, 4]

示例3：生成所有子集 (Subsets)

def subsets(nums):
    """
    生成一个列表的所有子集（幂集）。
    :param nums: 不含重复元素的列表
    :return: 所有子集的列表
    """
    result = []
    path = []

    def backtrack(start):
        # 收集当前路径（注意：包括空集）
        result.append(path[:])

        # 从start开始，尝试添加元素
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)  # 从下一个位置开始，避免重复
            path.pop()

    backtrack(0)
    return result

# 测试
nums = [1, 2, 3]
print(f"输入: {nums}")
print("所有子集:")
subset_result = subsets(nums)
for s in subset_result:
    print(s)

输出：

输入: [1, 2, 3]
所有子集:
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[2]
[2, 3]
[3]

实践练习

练习1：生成全排列（无重复数字）

题目：给定一个不含重复数字的列表 nums，返回其所有可能的全排列。你可以使用本课示例1的模板。 要求：输入 [1, 2]，输出应为 [[1,2], [2,1]]。

练习2：组合总和 II

题目：给定一个可能有重复的候选数字列表 candidates 和一个目标数 target。找出 candidates 中所有可以使数字和为 target 的组合。candidates 中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。 提示：

1. 这是一个组合问题，顺序不重要。
2. 因为有重复元素且要求组合不重复，需要先对数组排序，然后在递归时使用 start 索引。
3. 在遍历同一层级时，如果当前数字与前一个数字相同，并且前一个数字未被选择，则跳过当前数字，以避免产生重复组合。

示例：

输入: candidates = [10,1,2,7,6,1,5], target = 8
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

练习3：子集 II

题目：给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。 提示：

1. 这是一个子集问题。
2. 与练习2类似，需要先排序，然后在递归的循环中进行“去重”处理：if i > start and nums[i] == nums[i-1]: continue。

示例：

输入: nums = [1,2,2]
输出:
[
[],
[1],
[1,2],
[1,2,2],
[2],
[2,2]
]

常见错误

1. 混淆 start 和 i 的使用：

   • 在全排列中，每次都是从 0 或 1 开始遍历所有位置，但要检查元素是否被用过 (used 数组)。
   • 在组合和子集中，递归调用时传入的起始索引应该是 i + 1，而不是 start + 1。传 i + 1 是为了保证不重复选择同一个元素，并且保证了组合的顺序性（例如，只有 [1,2] 而没有 [2,1]）。

2. 忘记回溯：

   • 在 path.append(...) 之后调用了 backtrack()，但之后忘记写 path.pop()。这会导致所有路径共享同一个列表对象，最终结果全部是空或者乱码。

3. 处理重复元素不当：

   • 当输入有重复数字时，直接使用基本的排列或组合算法会导致结果集中出现重复的解。
   • 解决方案：先对数组排序。在同一层级的循环中，检查 nums[i] == nums[i-1] 时，需要确保 i > start 且 nums[i-1] 未被选择（对于组合/子集）或已被选择（取决于具体逻辑）。这是回溯法中常用的“剪枝”技巧。

4. 收集结果时的引用问题：

   • 在将 path 加入 result 时，直接使用 result.append(path) 是错误的，因为后续对 path 的修改会影响 result 中已存储的结果。必须使用 result.append(path[:]) 或 result.append(list(path)) 来创建一份拷贝。

小结

• 全排列：关注顺序，使用 used 数组标记元素是否被访问过，递归时从第一个元素开始扫描。
• 组合：不关注顺序，使用 start 参数确保每次从当前索引之后开始选择，避免重复和顺序问题。
• 子集：是组合问题的特例，在递归的每个阶段都收集当前路径，并使用 start 参数。
• 核心框架：无论排列、组合还是子集，其本质都是回溯。回溯算法可以抽象为以下模板：

  def backtrack(路径, 选择列表):
      if 满足结束条件:
          收集结果
          return
      for 选择 in 选择列表:
          做出选择
          backtrack(路径, 选择列表) # 递归
          撤销选择 # 回溯
  

  复制+ 追加到编辑器
• 处理重复：当输入有重复元素时，先排序，并在循环中检查相邻元素，利用“剪枝”条件避免生成重复的结果。

掌握了全排列和组合的回溯模式，你就能解决一大类关于“搜索”、“穷举”和“方案生成”的算法问题。下一课，我们将进入一个更有趣的挑战：数独变体与剪枝，继续深入探索回溯算法的威力与优化技巧。