用 Python 快速编写算法暴力验证程序

在 Codeforces 或其他算法竞赛中，我们经常会得到一个看起来正确的贪心、DP 或数学结论，但暂时无法完全证明它。此时最实用的办法不是继续盯着正解，而是写一个只处理小数据的暴力程序，直接按照题意枚举所有可能，再比较答案。

暴力验证程序和正式提交的代码有不同目标：

正解追求更低的时间复杂度；
验证程序追求简单、直接、容易人工检查；
正解可能使用复杂结论，验证程序应尽量只使用题目定义；
验证程序只处理很小的数据，不需要考虑正式数据范围。

Python 的列表、集合、生成器和 itertools 可以大幅减少枚举代码。因此，即使平时主要使用 C++，也只需要掌握一小部分 Python，就能快速写出可靠的验证程序。

本文的目标

本文不是完整的 Python 教程。它假设读者已经理解 C++、DFS、BFS 和复杂度，只讲如何把熟悉的暴力思路快速翻译成 Python。

1. 验证程序的基本结构

一个暴力验证程序通常只有三个部分：

生成候选：枚举所有可能的区间、子集、排列或操作序列。
判断合法：丢弃不满足题目条件的候选。
计算答案：判断是否存在合法方案，或者在合法方案中求最大值、最小值。

例如，判断数组中是否存在两个不同位置，使它们的和等于 target：

 1def two_sum_exists(a, target):
 2    n = len(a)
 3
 4    for i in range(n):
 5        for j in range(i + 1, n):
 6            if a[i] + a[j] == target:
 7                return True
 8
 9    return False
10
11
12assert two_sum_exists([2, 7, 11, 15], 9)
13assert not two_sum_exists([1, 2, 3], 10)

这段代码几乎就是 C++ 的直接翻译，只需要注意几个语法差异：

Python 使用缩进表示代码块，不写 {}。
def 定义函数，函数参数和变量通常不用写类型。
len(a) 相当于 a.size()。
range(n) 依次产生 0, 1, ..., n - 1。
range(l, r) 左闭右开，依次产生 l, l + 1, ..., r - 1。
True 和 False 对应 C++ 的 true 和 false。

上面的程序枚举了所有满足 $i<j$ 的点对，状态数量是 $O(n^2)$ 。它当然不适合正式数据，但非常适合验证哈希表或双指针写出的正解。

验证程序首先要可信

不要急着把暴力写成一行。先写成与题意直接对应的循环，确认正确以后，再使用 Python 的简洁写法。

2. 枚举点对与区间

2.1 使用 `range` 枚举点对

竞赛中常见的点对有两种：

 1a = [10, 20, 30]
 2n = len(a)
 3
 4# 有序点对：(i, j) 和 (j, i) 被视为不同方案
 5ordered_pairs = []
 6for i in range(n):
 7    for j in range(n):
 8        if i != j:
 9            ordered_pairs.append((i, j))
10
11# 无序点对：只枚举 i < j
12unordered_pairs = []
13for i in range(n):
14    for j in range(i + 1, n):
15        unordered_pairs.append((i, j))
16
17assert len(ordered_pairs) == 6
18assert len(unordered_pairs) == 3

这里的 (i, j) 是一个 tuple，也就是元组。元组与 C++ 的 pair 类似，可以存放多个值；与 Python 列表不同，元组创建后不能修改。

2.2 使用 `enumerate` 同时取得下标和值

C++ 经常写：

1for (int i = 0; i < a.size(); ++i) {
2    int x = a[i];
3}

Python 可以使用 enumerate：

1a = [10, 20, 30]
2items = []
3
4for i, x in enumerate(a):
5    items.append((i, x))
6
7assert items == [(0, 10), (1, 20), (2, 30)]

for i, x in ... 使用了元组解包。enumerate(a) 每次产生 (下标, 元素)，Python 自动把它拆到 i 和 x 中。

2.3 使用切片枚举区间

Python 的切片 a[l:r] 会得到下标范围 $[l,r)$ 内的新列表：

1a = [3, -2, 5, -1]
2
3assert a[1:3] == [-2, 5]
4assert a[:2] == [3, -2]       # 省略 l，表示从 0 开始
5assert a[2:] == [5, -1]       # 省略 r，表示直到末尾
6assert a[::-1] == [-1, 5, -2, 3]  # 步长为 -1，表示翻转

下面按照定义枚举所有非空子数组，求最大子数组和：

 1def max_subarray_brute(a):
 2    if not a:
 3        return 0
 4
 5    ans = a[0]
 6    n = len(a)
 7
 8    for left in range(n):
 9        for right in range(left + 1, n + 1):
10            segment = a[left:right]
11            ans = max(ans, sum(segment))
12
13    return ans
14
15
16assert max_subarray_brute([3, -2, 5, -1]) == 6
17assert max_subarray_brute([-5, -2, -8]) == -2
18assert max_subarray_brute([]) == 0

共有 $O(n^2)$ 个区间，而 sum(segment) 又需要 $O(n)$ ，所以这个写法的总复杂度是 $O(n^3)$ 。作为小数据验证程序，它比维护前缀和更接近“直接计算每个区间的和”的定义，因此更容易确认正确。

3. 筛选候选与整体判定

Python 最值得掌握的不是某个复杂库，而是把“遍历、筛选、计算”写得接近数学定义。

3.1 列表推导式

下面两段代码完全等价：

 1a = [-3, 1, 4, -2, 5]
 2
 3positive = []
 4for x in a:
 5    if x > 0:
 6        positive.append(x)
 7
 8positive_short = [x for x in a if x > 0]
 9
10assert positive == [1, 4, 5]
11assert positive_short == positive

列表推导式的一般形式是：

1[要放入列表的表达式 for 元素 in 可迭代对象 if 条件]

它非常适合从一个候选状态中取出被选择的元素：

1a = [5, 8, 13, 21]
2selected = [True, False, True, False]
3
4subset = [x for x, use in zip(a, selected) if use]
5
6assert subset == [5, 13]

zip(a, selected) 每次同时取出两个序列的对应元素，类似同时移动两个 C++ 迭代器。需要注意，zip 会在较短的序列结束时停止。

3.2 生成器表达式

把列表推导式的 [] 改成 ()，就得到生成器表达式：

1a = [1, 2, 3, 4]
2
3squares_list = [x * x for x in a]
4squares_generator = (x * x for x in a)
5
6assert squares_list == [1, 4, 9, 16]
7assert sum(squares_generator) == 30

列表推导式会立即创建整个列表；生成器只在需要时逐个产生元素。验证程序中，生成器经常直接交给 sum、min、max、any 或 all，不需要保存所有中间结果。

生成器的惰性求值、一次性消费和短路复杂度，见Python 生成器表达式。

3.3 使用 `any` 和 `all` 表达存在与全称

any(...)：只要存在一个元素为真，就返回 True。
all(...)：只有所有元素都为真，才返回 True。

例如检查数组是否严格递增：

1def is_strictly_increasing(a):
2    return all(x < y for x, y in zip(a, a[1:]))
3
4
5assert is_strictly_increasing([1, 3, 8])
6assert not is_strictly_increasing([1, 3, 3])
7assert is_strictly_increasing([])

zip(a, a[1:]) 会产生所有相邻元素对。all 遇到第一个 False 就停止，any 遇到第一个 True 就停止，这叫短路求值。

空序列上的结果

any([]) 是 False，因为不存在满足条件的元素；all([]) 是 True，因为没有元素违反条件。这与数学中的存在量词和全称量词一致。

4. 枚举子集

长度为 $n$ 的集合有 $2^n$ 个子集。写验证程序时，通常有位掩码和 itertools.product 两种方法。

4.1 位掩码：最接近 C++ 的写法

下面暴力验证 0/1 背包：

 1def knapsack_brute_mask(weights, values, capacity):
 2    n = len(weights)
 3    best = 0
 4
 5    for mask in range(1 << n):
 6        total_weight = 0
 7        total_value = 0
 8
 9        for i in range(n):
10            if mask >> i & 1:
11                total_weight += weights[i]
12                total_value += values[i]
13
14        if total_weight <= capacity:
15            best = max(best, total_value)
16
17    return best
18
19
20assert knapsack_brute_mask([2, 3, 4], [3, 4, 5], 6) == 8
21assert knapsack_brute_mask([], [], 10) == 0

这里的 1 << n、mask >> i & 1 与 C++ 完全相同。它适合把已有的位运算思路直接搬到 Python。

4.2 `product`：把多层循环写成状态选择

itertools.product 计算笛卡尔积。product([False, True], repeat=n) 表示每个位置都从“不选、选”两种状态中选择一次：

 1from itertools import product
 2
 3
 4def knapsack_brute_product(weights, values, capacity):
 5    n = len(weights)
 6    best = 0
 7
 8    for selected in product([False, True], repeat=n):
 9        total_weight = sum(
10            weight
11            for weight, use in zip(weights, selected)
12            if use
13        )
14
15        if total_weight <= capacity:
16            total_value = sum(
17                value
18                for value, use in zip(values, selected)
19                if use
20            )
21            best = max(best, total_value)
22
23    return best
24
25
26assert knapsack_brute_product([2, 3, 4], [3, 4, 5], 6) == 8
27assert knapsack_brute_product([], [], 10) == 0

如果每个位置不止两种状态，product 比位掩码更加自然。例如把每个物品分配给 A、B 或不选择，一共有 $3^n$ 种状态：

1from itertools import product
2
3states = list(product([0, 1, 2], repeat=2))
4
5assert len(states) == 3 ** 2
6assert (0, 0) in states
7assert (2, 1) in states

product 返回的是迭代器，每次产生一个元组。不要在大状态空间上随意套 list(...)；上面转换成列表只是为了演示。

5. 枚举排列与组合

5.1 `permutations`：枚举顺序

如果题目关心元素的执行顺序，可以使用 itertools.permutations。例如用全排列验证旅行商问题的最短回路：

 1from itertools import permutations
 2
 3
 4def tsp_brute(dist):
 5    n = len(dist)
 6    if n <= 1:
 7        return 0
 8
 9    best = None
10
11    # 固定从 0 出发，只排列剩下的点
12    for order in permutations(range(1, n)):
13        route = (0,) + order + (0,)
14        cost = sum(
15            dist[route[i]][route[i + 1]]
16            for i in range(len(route) - 1)
17        )
18
19        if best is None or cost < best:
20            best = cost
21
22    return best
23
24
25dist = [
26    [0, 10, 15, 20],
27    [10, 0, 35, 25],
28    [15, 35, 0, 30],
29    [20, 25, 30, 0],
30]
31
32assert tsp_brute(dist) == 80
33assert tsp_brute([]) == 0

(0,) 是只有一个元素的元组。单元素元组必须带逗号，否则 (0) 只是整数 0。

全排列共有 $n!$ 种。 $8!=40320$ ，但 $10!=3628800$ ，如果还要重复验证很多组数据，增长会非常快。实际验证时通常把排列规模控制在 $n\leq 8$ 左右。

5.2 `combinations`：只关心选择，不关心顺序

从 $n$ 个元素中选择 $k$ 个、不区分顺序时，使用 combinations：

 1from itertools import combinations
 2
 3
 4def best_k_sum_not_exceed(a, k, limit):
 5    best = None
 6
 7    for chosen in combinations(a, k):
 8        current = sum(chosen)
 9        if current <= limit:
10            if best is None or current > best:
11                best = current
12
13    return best
14
15
16assert best_k_sum_not_exceed([2, 4, 7, 9], 2, 13) == 13
17assert best_k_sum_not_exceed([8, 9], 2, 5) is None

combinations(a, k) 产生 $\binom{n}{k}$ 个元组。没有合法方案时，上面的函数返回 None，类似 C++ 的 optional 或一个专门表示“无解”的值。

如果允许同一个候选值被选择多次，可以使用 combinations_with_replacement：

1from itertools import combinations_with_replacement
2
3choices = list(combinations_with_replacement([1, 2, 3], 2))
4
5assert choices == [
6    (1, 1), (1, 2), (1, 3),
7    (2, 2), (2, 3),
8    (3, 3),
9]

重复元素与重复排列

permutations([1, 1, 2]) 按位置排列，因此会产生内容相同的元组。小数据下可以写 set(permutations(a)) 去重，但它仍会枚举全部位置排列，并保存所有不同的结果。更大的状态空间应在搜索过程中跳过重复选择。

相邻元素、前缀聚合和连接迭代器等工具，见Python itertools 实用组合。

6. 选择依赖当前状态：DFS 与回溯

product 适合每个位置的候选集合固定不变。如果下一步能选什么取决于当前状态，就需要 DFS 和回溯。

例如生成所有长度为 $2n$ 的合法括号序列：

 1def generate_parentheses(n):
 2    answer = []
 3    path = []
 4
 5    def dfs(left, right):
 6        if left == n and right == n:
 7            answer.append("".join(path))
 8            return
 9
10        if left < n:
11            path.append("(")
12            dfs(left + 1, right)
13            path.pop()
14
15        if right < left:
16            path.append(")")
17            dfs(left, right + 1)
18            path.pop()
19
20    dfs(0, 0)
21    return answer
22
23
24assert generate_parentheses(0) == [""]
25assert generate_parentheses(3) == [
26    "((()))",
27    "(()())",
28    "(())()",
29    "()(())",
30    "()()()",
31]

这里最重要的模式是：

1选择：path.append(choice)
2递归：dfs(...)
3撤销：path.pop()

Python 的 list 是可变对象，所有递归层看到的是同一个 path。如果递归返回后不执行 pop()，上一个分支留下的选择就会污染下一个分支。

终点处使用 "".join(path)，会把字符列表连接成一个新字符串。也可以使用 path.copy() 保存当前列表的副本；不能直接 answer.append(path)，否则答案中的所有元素都会指向同一个列表。

7. 枚举状态图：BFS

如果每种状态都能通过若干操作转移到新状态，并且需要验证最少操作次数，可以在小状态空间上直接 BFS。

例如：每次只能交换相邻元素，求把一个短数组变成目标数组的最少交换次数。

 1from collections import deque
 2
 3
 4def min_adjacent_swaps(start, target):
 5    start = tuple(start)
 6    target = tuple(target)
 7
 8    if sorted(start) != sorted(target):
 9        return None
10    if start == target:
11        return 0
12
13    queue = deque([(start, 0)])
14    visited = {start}
15
16    while queue:
17        state, distance = queue.popleft()
18
19        for i in range(len(state) - 1):
20            next_state = list(state)
21            next_state[i], next_state[i + 1] = (
22                next_state[i + 1],
23                next_state[i],
24            )
25            next_state = tuple(next_state)
26
27            if next_state == target:
28                return distance + 1
29
30            if next_state not in visited:
31                visited.add(next_state)
32                queue.append((next_state, distance + 1))
33
34    return None
35
36
37assert min_adjacent_swaps([3, 1, 2], [1, 2, 3]) == 2
38assert min_adjacent_swaps([1, 2], [1, 2]) == 0
39assert min_adjacent_swaps([1, 2], [1, 3]) is None

这里用到了三个重要的数据结构：

deque：双端队列，popleft() 可以 $O(1)$ 弹出队首，适合 BFS；
set：哈希集合，平均 $O(1)$ 判断状态是否访问过；
tuple：不可修改，可以放进 set，而 list 不能作为哈希键。

如果还需要记录每个状态的距离、来源或答案，可以使用 dict：

1distance = {(1, 2, 3): 0}
2distance[(2, 1, 3)] = 1
3
4assert distance[(2, 1, 3)] == 1
5assert (3, 2, 1) not in distance

关于 Counter、defaultdict、deque、dict 和 set 的选择，见Python 竞赛常用容器。

8. 消除重复搜索：记忆化

有些递归暴力会反复遇到相同状态。此时可以使用 functools.cache 保存“状态到答案”的映射。

例如，在每个数前添加 + 或 -，统计有多少种符号分配能得到目标值：

 1from functools import cache
 2
 3
 4def count_sign_assignments(a, target):
 5    @cache
 6    def dfs(index, current_sum):
 7        if index == len(a):
 8            return int(current_sum == target)
 9
10        return (
11            dfs(index + 1, current_sum + a[index])
12            + dfs(index + 1, current_sum - a[index])
13        )
14
15    return dfs(0, 0)
16
17
18assert count_sign_assignments([1, 1, 1, 1, 1], 3) == 5
19assert count_sign_assignments([], 0) == 1
20assert count_sign_assignments([], 1) == 0

不使用缓存时，递归树有 $2^n$ 个叶子。加入 cache 后，每个不同的 (index, current_sum) 只计算一次。这已经接近记忆化 DP，但代码仍然保持了“枚举当前位置放正号或负号”的暴力结构，很适合用来验证更复杂的推导。

cache 的参数必须可以哈希。整数、字符串和只包含可哈希元素的元组可以作为参数，列表不可以。如果状态原来是列表，可以在调用前转成 tuple(state)。

Python 版本

functools.cache 从 Python 3.9 开始提供。旧版本可以使用 functools.lru_cache(maxsize=None)，含义相同。

9. 从候选方案得到答案

生成候选以后，常见目标可以归纳成几种操作：

目标	Python 写法
求和	`sum(candidates)`
最大值	`max(candidates)`
最小值	`min(candidates)`
是否存在	`any(condition(x) for x in candidates)`
是否全部满足	`all(condition(x) for x in candidates)`
找到第一个方案或反例	`next(generator, default)`

例如，寻找一个和恰好等于数组总和一半的子集：

 1from itertools import combinations
 2
 3
 4def find_equal_partition(a):
 5    total = sum(a)
 6    if total % 2 != 0:
 7        return None
 8
 9    target = total // 2
10
11    for size in range(len(a) + 1):
12        answer = next(
13            (
14                chosen
15                for chosen in combinations(a, size)
16                if sum(chosen) == target
17            ),
18            None,
19        )
20        if answer is not None:
21            return answer
22
23    return None
24
25
26assert find_equal_partition([1, 5, 11, 5]) == (11,)
27assert find_equal_partition([1, 2, 5]) is None
28assert find_equal_partition([]) == ()

next(generator, None) 返回生成器产生的第一个元素；如果没有元素，则返回 None。因此它不仅能回答“是否存在”，还能给出一个具体方案或反例。

min 和 max 默认不能处理空序列。候选集合可能为空时，可以先判断，或者使用 default：

1assert max([], default=0) == 0
2assert min([], default=None) is None

default 应根据题意选择，不能一律写成 0。例如所有合法答案都可能是负数时，0 也许不是合法答案。

10. Python 验证代码的常见陷阱

验证程序本身也可能出错。下面这些问题尤其容易让熟悉 C++ 的读者误判。

10.1 赋值不是复制

 1a = [1, 2, 3]
 2b = a
 3b.append(4)
 4
 5assert a == [1, 2, 3, 4]
 6assert a is b
 7
 8c = a.copy()
 9c.append(5)
10
11assert a == [1, 2, 3, 4]
12assert c == [1, 2, 3, 4, 5]

b = a 只是让两个变量指向同一个列表。a.copy() 或 a[:] 可以复制一层；如果列表内部还有列表，并且也需要完全独立，应使用 copy.deepcopy()。

10.2 不要用乘法创建二维列表

 1wrong = [[0] * 3] * 2
 2wrong[0][0] = 7
 3
 4# 两行实际指向同一个内部列表
 5assert wrong == [[7, 0, 0], [7, 0, 0]]
 6
 7correct = [[0] * 3 for _ in range(2)]
 8correct[0][0] = 7
 9
10assert correct == [[7, 0, 0], [0, 0, 0]]

10.3 列表不能放进集合

1visited = set()
2state = [1, 2, 3]
3
4visited.add(tuple(state))
5
6assert (1, 2, 3) in visited

集合中的元素必须可哈希。列表可能被修改，因此不能直接放进 set；元组不可修改，可以用作状态表示。

10.4 生成器只能消费一次

1numbers = (x * x for x in range(4))
2
3assert sum(numbers) == 14
4assert sum(numbers) == 0  # 第一次 sum 已经把生成器取完

需要多次遍历时，应重新创建生成器，或者在状态规模很小时转换成列表。

10.5 全排列可能重复

1from itertools import permutations
2
3all_orders = list(permutations([1, 1, 2]))
4unique_orders = set(all_orders)
5
6assert len(all_orders) == 6
7assert len(unique_orders) == 3

permutations 排列的是位置，而不是不同的值。验证程序规模很小时可以用集合去重，但必须意识到它先枚举了全部 $n!$ 个排列。

10.6 回溯后必须恢复状态

凡是递归中修改了共享的列表、集合或字典，都要检查递归返回后是否恢复了现场。常见的成对操作包括：

1append  <-> pop
2add     <-> remove
3赋新值  <-> 恢复旧值

如果不想在原状态上修改，也可以为下一层创建新状态，但代码要明确知道复制的是一层还是深层。

11. 用验证函数检查正解

掌握上面的写法后，对拍本身反而是最简单的一步：对同一份小数据分别调用暴力函数和待验证函数，然后使用 assert 比较。

下面用 $O(n^3)$ 的区间枚举验证 $O(n)$ 的最大子数组和算法：

 1from random import Random
 2
 3
 4def max_subarray_brute(a):
 5    if not a:
 6        return 0
 7
 8    answer = a[0]
 9    for left in range(len(a)):
10        for right in range(left + 1, len(a) + 1):
11            answer = max(answer, sum(a[left:right]))
12    return answer
13
14
15def max_subarray_fast(a):
16    if not a:
17        return 0
18
19    current = a[0]
20    answer = a[0]
21
22    for x in a[1:]:
23        current = max(x, current + x)
24        answer = max(answer, current)
25
26    return answer
27
28
29rng = Random(20260715)
30
31for case_id in range(1000):
32    n = rng.randint(0, 8)
33    a = [rng.randint(-10, 10) for _ in range(n)]
34
35    expected = max_subarray_brute(a)
36    actual = max_subarray_fast(a)
37
38    assert actual == expected, (
39        f"case={case_id}, a={a}, "
40        f"expected={expected}, actual={actual}"
41    )

这里使用独立的 Random 对象和固定种子。只要代码不变，每次运行都会生成相同的数据，出现错误时就能稳定复现。

如何生成边界数组、合法区间、树和简单图，见用 Python 生成可复现的随机测试数据。

这个例子说明，对拍流程并不是重点。真正需要练习的是前面的 max_subarray_brute：能否快速把题目定义写成简单、独立、值得信任的 Python 程序。

12. 如何选择枚举方式

要枚举的对象	常用写法	状态数量
所有点对	两层 `for`	$O(n^2)$
所有区间	`left`、`right` 两层循环	$O(n^2)$ 个区间
所有子集	位掩码或 `product`	$2^n$
每个位置 $k$ 种状态	`product(range(k), repeat=n)`	$k^n$
选择 $k$ 个元素	`combinations`	$\binom{n}{k}$
所有顺序	`permutations`	$n!$
下一步依赖当前状态	DFS + 回溯	取决于搜索树
最少操作次数	`deque` + BFS	取决于状态图
大量重复子问题	DFS + `cache`	取决于不同状态数

不要死记“Python 能跑到多大的 $n$ ”。验证程序的总耗时还取决于单个状态的计算量和需要测试多少组数据。更稳妥的做法是从很小的 $n$ 开始，确认能够快速运行后再逐渐增大。

总结

使用 Python 写暴力验证程序，最值得掌握的不是完整语法，而是几种能够直接表达状态空间的工具：

用 range、enumerate 和切片枚举点对与区间；
用列表推导式和生成器筛选、转换候选；
用 any、all、sum、min、max、next 表达判定和答案；
用位掩码、product、permutations、combinations 枚举规则状态空间；
用 DFS、回溯、BFS 和 cache 处理依赖当前状态的搜索；
用 tuple、set、dict 和 deque 表示、判重和管理状态；
时刻注意可变对象、复制、状态恢复和空候选集合。

一个好的验证程序不需要聪明。它应该尽量接近题目定义，让你能一眼确认每个候选都被枚举、每个条件都被检查。Python 的价值，就是让这种直接写法足够短，能够在比赛中迅速完成。

用 Python 快速编写算法暴力验证程序

1. 验证程序的基本结构

2. 枚举点对与区间

2.1 使用 `range` 枚举点对

2.2 使用 `enumerate` 同时取得下标和值

2.3 使用切片枚举区间

3. 筛选候选与整体判定

3.1 列表推导式

3.2 生成器表达式

3.3 使用 `any` 和 `all` 表达存在与全称

4. 枚举子集

4.1 位掩码：最接近 C++ 的写法

4.2 `product`：把多层循环写成状态选择

5. 枚举排列与组合

5.1 `permutations`：枚举顺序

5.2 `combinations`：只关心选择，不关心顺序

6. 选择依赖当前状态：DFS 与回溯

7. 枚举状态图：BFS

8. 消除重复搜索：记忆化

9. 从候选方案得到答案

10. Python 验证代码的常见陷阱

10.1 赋值不是复制

10.2 不要用乘法创建二维列表

10.3 列表不能放进集合

10.4 生成器只能消费一次

10.5 全排列可能重复

10.6 回溯后必须恢复状态

11. 用验证函数检查正解

12. 如何选择枚举方式

相关专题

总结

参考资料

用 Python 快速编写算法暴力验证程序

1. 验证程序的基本结构

2. 枚举点对与区间

2.1 使用 range 枚举点对

2.2 使用 enumerate 同时取得下标和值

2.3 使用切片枚举区间

3. 筛选候选与整体判定

3.1 列表推导式

3.2 生成器表达式

3.3 使用 any 和 all 表达存在与全称

4. 枚举子集

4.1 位掩码：最接近 C++ 的写法

4.2 product：把多层循环写成状态选择

5. 枚举排列与组合

5.1 permutations：枚举顺序

5.2 combinations：只关心选择，不关心顺序

6. 选择依赖当前状态：DFS 与回溯

7. 枚举状态图：BFS

8. 消除重复搜索：记忆化

9. 从候选方案得到答案

10. Python 验证代码的常见陷阱

10.1 赋值不是复制

10.2 不要用乘法创建二维列表

10.3 列表不能放进集合

10.4 生成器只能消费一次

10.5 全排列可能重复

10.6 回溯后必须恢复状态

11. 用验证函数检查正解

12. 如何选择枚举方式

相关专题

总结

参考资料

2.1 使用 `range` 枚举点对

2.2 使用 `enumerate` 同时取得下标和值

3.3 使用 `any` 和 `all` 表达存在与全称

4.2 `product`：把多层循环写成状态选择

5.1 `permutations`：枚举顺序

5.2 `combinations`：只关心选择，不关心顺序