排列与组合
枚举列表中有重复元素和无重复元素时的所有排列，并生成所有 k 组合及组合求和变体。
排列与组合 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
排列与组合
排列是顺序很重要的排列方式：[1,2,3] 和 [3,2,1] 被视为不同结果。n 个项目的排列数量为 n!。组合是顺序不重要的选择：选择 {1,2} 与选择 {2,1} 相同。从 n 个项目中选择 k 个项目的数量为 C(n,k) = n! / (k! × (n-k)!)。这两种模式对于面试中涉及计数、枚举和选择的问题都非常重要。
import math
# Permutations
n = 4
print(f'Permutations of {n} items: {math.factorial(n)}')
# 4! = 24
# Combinations
for k in range(n+1):
print(f'C({n},{k}) = {math.comb(n,k)}')
# C(4,0)=1, C(4,1)=4, C(4,2)=6, C(4,3)=4, C(4,4)=1
# Sum = 2^4 = 16 (total subsets)生成所有排列
使用 used 布尔数组跟踪当前路径中包含的元素。每一步都尝试每个尚未使用的元素。探索完成后，再次将该元素标记为未使用。与子集不同，排列不需要 start 索引，因为排列可以按任意顺序使用元素。当 len(path) == n 时，递归到达终点。
def permutations(nums):
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i, num in enumerate(nums):
if not used[i]:
used[i] = True # CHOOSE
path.append(num)
backtrack(path) # EXPLORE
path.pop() # UNCHOOSE
used[i] = False
backtrack([])
return result
print(permutations([1, 2, 3]))
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]基于交换的排列
另一种方法是：将位置 start 上的元素依次与从 start 到 n-1 的每个元素交换，进行递归，然后交换回来。这种方法直接原地修改数组，不需要 used 数组。关键洞察是：在每一层中，start 左侧的所有元素都已固定，我们要选择哪个元素放到位置 start。这种方法的内存效率略高，也是堆算法的基础。
def permutations_swap(nums):
result = []
def backtrack(start):
if start == len(nums):
result.append(list(nums))
return
for i in range(start, len(nums)):
nums[start], nums[i] = nums[i], nums[start] # CHOOSE (swap)
backtrack(start + 1) # EXPLORE
nums[start], nums[i] = nums[i], nums[start] # UNCHOOSE (swap back)
backtrack(0)
return result
print(permutations_swap([1, 2, 3]))
# Same 6 permutations, different order排列 II：处理重复项
当输入包含重复项时（例如 [1, 1, 2]），使用 used 数组的方法会生成重复的排列。解决方法是：先对数组排序，然后在前一个相同元素未在本次递归调用中使用时跳过当前重复项。条件为：if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue。这样可以确保重复元素始终按照从左到右的顺序选择。
def permutations_unique(nums):
nums.sort()
result = []
used = [False] * len(nums)
def backtrack(path):
if len(path) == len(nums):
result.append(list(path))
return
for i in range(len(nums)):
if used[i]: continue
# Skip if this num is a duplicate and the previous dup was not used
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
used[i] = True
path.append(nums[i])
backtrack(path)
path.pop()
used[i] = False
backtrack([])
return result
print(permutations_unique([1, 1, 2]))
# [[1,1,2],[1,2,1],[2,1,1]] — 3, not 6下一个排列（字典序）
下一个排列（LeetCode 31）将数组原地转换为按字典序排列的下一个更大排列。算法如下：（1）找到满足 nums[i] < nums[i+1] 的最右侧索引 i。（2）找到满足 nums[j] > nums[i] 的最右侧索引 j。（3）交换 nums[i] 和 nums[j]。（4）反转索引 i 之后的后缀。如果不存在这样的 i，则反转整个数组（回到最小排列）。
def next_permutation(nums):
n = len(nums)
# Step 1: find rightmost i where nums[i] < nums[i+1]
i = n - 2
while i >= 0 and nums[i] >= nums[i+1]:
i -= 1
if i >= 0:
# Step 2: find rightmost j where nums[j] > nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Step 3: swap
nums[i], nums[j] = nums[j], nums[i]
# Step 4: reverse suffix after i
nums[i+1:] = nums[i+1:][::-1]
return nums
print(next_permutation([1, 2, 3])) # [1,3,2]
print(next_permutation([3, 2, 1])) # [1,2,3] (wraps)
print(next_permutation([1, 1, 5])) # [1,5,1]k-组合回溯
生成 n 个元素中所有由 k 个元素组成的 combinations（LeetCode 77）。使用起始索引（类似于 subsets）来避免重复访问元素，并保持排序顺序。当剩余元素少于 k - len(path) 个时进行剪枝：if len(nums) - i + 1 < k - len(path): break。这与之前的 combine(n, k) 等价，只是现在操作的是实际数组。
def combinations(nums, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
for i in range(start, len(nums)):
# Pruning: not enough elements left
if len(nums) - i < k - len(path):
break
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(combinations([1,2,3,4,5], 3))
# 10 combinations: C(5,3)
import math
print(math.comb(5,3)) # 10组合总和：无限次复用
组合总和（LeetCode 39）允许每个数字被无限次使用。它与标准 combinations 的区别在于：不将 start 前进到 i+1，而是传入 i（相同索引），从而允许复用当前元素。剪枝规则是：如果剩余目标值变为 0，就记录路径；如果变为负数，就停止。排序可以在所有剩余候选值都大于剩余目标值时提前终止。
def combination_sum(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
c = candidates[i]
if c > remaining: break # all remaining are too big
path.append(c)
backtrack(i, path, remaining - c) # reuse allowed: pass i, not i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7))
# [[2,2,3],[7]]组合总和 II：不复用，含重复项
组合总和 II（LeetCode 40）中每个数字最多使用一次，但输入可能包含重复项。它结合了两种技术：将 start 前进到 i+1（不复用），并在排序后跳过同一层级中的重复项（if i > start and nums[i] == nums[i-1]: continue）。这是 subsets II 中的重复项处理方式与 combinations 中的不复用约束的结合。
def combination_sum_ii(candidates, target):
candidates.sort()
result = []
def backtrack(start, path, remaining):
if remaining == 0:
result.append(list(path))
return
for i in range(start, len(candidates)):
if candidates[i] > remaining: break
# Skip duplicates at same level
if i > start and candidates[i] == candidates[i-1]:
continue
path.append(candidates[i])
backtrack(i + 1, path, remaining - candidates[i]) # no reuse: i+1
path.pop()
backtrack(0, [], target)
return result
print(combination_sum_ii([10,1,2,7,6,1,5], 8))
# [[1,1,6],[1,2,5],[1,7],[2,6]]电话号码的字母组合
字母组合（LeetCode 17）将每个数字映射到手机键盘上的字母，并生成给定数字字符串的所有可能字母组合。这是一个回溯问题：在每个位置选择该数字映射中的一个字母，然后进行递归。对于长度为 n、每个数字平均对应 k 个字母的字符串，其 time 复杂度为 O(kⁿ)。
def letter_combinations(digits):
if not digits: return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
result = []
def backtrack(index, path):
if index == len(digits):
result.append(''.join(path))
return
for letter in phone[digits[index]]:
path.append(letter)
backtrack(index + 1, path)
path.pop()
backtrack(0, [])
return result
print(letter_combinations('23'))
# ['ad','ae','af','bd','be','bf','cd','ce','cf']排列与组合的比较
关键结构差异如下：排列——没有起始索引，使用 used 数组或交换来避免重复使用，树在每一层有 n 个选择，共有 n! 个叶节点。组合——使用起始索引来保证顺序，共有 C(n,k) 个叶节点。组合总和——不推进起始索引以允许复用，并根据目标值进行剪枝。将任何新问题映射到这三种形式之一，就能立即得到正确的模板。
# Pattern summary:
# Permutations: for i in range(n); if not used[i]; no start advancement
# Combinations: for i in range(start, n); advance start → i+1
# Combo Sum (reuse): for i in range(start, n); advance start → i (same)
# Quick reference:
import math
n = 5
print(f'Perm({n}) = n! = {math.factorial(n)}')
print(f'Comb({n},2) = C(n,k) = {math.comb(n,2)}')
print(f'Comb({n},3) = {math.comb(n,3)}')
# Also: subsets = sum(C(n,k) for k=0..n) = 2^n
print(f'Subsets({n}) = 2^n = {2**n}')复杂度与面试技巧
枚举的时间复杂度为：排列 O(n × n!)，组合 O(k × C(n,k))，组合总和 O(n^(T/最小值))。空间复杂度为递归深度所需的 O(n)，加上存储结果所需的 O(输出)。关键技巧：（1）始终确认顺序是否重要（排列还是组合）。（2）在对方询问之前就说明如何处理重复项。（3）始终明确说明剪枝条件。（4）对于较大的 n，要指出输出本身就是指数级的——对于该任务而言，这种算法已经是最优的。
import math
# Complexity for n=10
n = 10
print(f'Permutations(10): {math.factorial(n):,} results')
print(f'Combinations(10,5): {math.comb(n,5):,} results')
print(f'Subsets(10): {2**n:,} results')
# For interview: state which pattern
# 'This is a combinations problem because order doesnt matter'
# 'I will use a start index to avoid revisiting elements'
# 'Pruning: when sum exceeds target, break (after sorting)'快速检查
请测试您对本课中“数据结构 & 算法——编程面试准备”概念的理解。
课程回顾
本课介绍了：permutations 使用 used 数组且不需要起始索引，可以生成 n! 种排列方式，combinations 使用不断前进的起始索引来避免复用，可以生成 C(n,k) 种选择，以及两个问题中的重复项都通过排序，并在相同递归层级跳过重复值来处理。接下来我们将把回溯应用于 N 皇后问题，并探索约束传播。
常见问题解答
「排列与组合」课时是免费的吗？
是的 — 「排列与组合」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「排列与组合」这节课中我会学到什么？
枚举列表中有重复元素和无重复元素时的所有排列，并生成所有 k 组合及组合求和变体。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「排列与组合」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。