穷举暴力求解很多时候就是解法。哪怕一些“看起来应该有巧妙方法”的可能真的没有。
在很多看起来数学意味比较浓的题目中，如果数据规模较小，可能就是要穷举。

直接穷举#

直接遍历所有的可能，生成+测试。但是这里涉及很多优化技巧，暴力不能真的完全暴力。

穷举什么？#

穷举什么可以让穷举量变小？依靠题目条件或问题的约束，选择更合适的穷举对象。

输入正整数 n，输出所有形如 abcde / fghij = n 的表达式。其中 aj 是09的一个排列，可以有前导0.

如果直接遍历所有排列有 10！=3628800 次。
但是依赖所求的约束，知道了 fghij 后可以直接反推出 n 倍的 abcde，再判断是否是排列即可。
遍历 fghij 时，发现需要的 abcde 超过了5位时可以直接终止枚举。

寻找乘积最大连续子序列

连续子序列 / 区间问题，最简单的暴力方法是枚举起点和终点。

约束穷举范围#

依然是挖掘题中约束。如何设计出这个范围非常考验经验与巧思。

输入正整数k，寻找所有正整数 x>=y， 1/k = 1/x + 1/y。

看似xy无穷无尽，实际上存在约束。1/x <= 1/y，则 1/k <= 1/y + 1/y，1/k <= 2/y, y<=2k。所以只用穷举小于等于2k的y，并判断作差后是否是符合条件的x即可。

DFS递归与回溯法#

主要就是回溯法。

子集构造#

在很多时候有用。

增量构造#

从小到大，每次挑一个元素放到子集中。

void subset(int n, int *A, int *S int cur)    //n是元素个数，A是全集数组(正序)，cur是当前有几个元素在子集中  
//注意只能越来越拿大的  
{  
	use_current_subset(S);   //直接用当前子集，什么也不加  
	int s = cur ? S[cur-1]+1 : 0; //s是新入子集的元素最小值  
	for(int i=0;i<n;i++){  
		if(A[i]>=s){  
			S[cur] = A[i];  
			subset(n, A, S, cur+1);  
		}  
	}  
}  

位向量法#

维护一个向量，维数为全集元素个数，1表示拿，0表示不拿。
递归地构造这个位向量，当前取0、当前取1，…
必须完整地构造完这个位向量（解答树到叶子）才能真正出子集。

二进制法#

位向量法的压位方法。一般全集元素个数不能多于16个。

回溯法#

在每次选择新元素时，选择不与已有解相冲突的，然后递归下一层。并且检验解。
构造问题，如
八皇后问题，素数环问题（把几个数编成一个环，相邻数和为质数），字符串构造问题…
把握回溯法“当前已有的”都是合法的，选择新元素的原则是新加入的元素不破坏合法性。

剪枝#

剪枝技巧是回溯法非常重要的技巧，能很大程度上改善效率。如果加深图中发现当前解已经不可能达到符合要求的解，则提前终止加深，返回。
一个常见的例子是需要搜索一个“最优”的情况，可以记录当前最优，在回溯搜索过程中，如果发现已有部分已经不能达到最优，就可以提前返回，终止继续加深，找下一个。
还有一种是乐观估计，如果已有当前解，剩下的不确定，在这种情况下乐观估计也无法达到更优（或者无法构造出解），就直接终止返回。这在IDA中很重要。

枚举二叉树#

有时候要构建一个符合要求的类似二叉树的解，它一般会给出叶子，要构建二叉树。
枚举二叉树的方法是每次选出两个“叶子”作为兄弟，上增一个父亲节点相连。然后新形成的子树当做整体，回到“叶子”队伍中。
像霍夫曼编码那样构建出一棵树。

迭代加深搜索与IDA#

迭代加深搜索像是DFS与回溯在无限问题上的改动。
有些问题DFS深度可以是无限的，就需要人为加上深度，每次最多只搜索到这么深，不断加深深度地搜索。
框架如下：

for(maxd = 1;;maxd++){  
	dfs(...,maxd);  
}  

埃及分数问题
用单位分数之和表示任意分数，搜索一个解。加数越少越好，最小的分数越大越好（最大的分母尽可能小）

这题是迭代加深搜索的典型。显然单位分数可以有无限长，DFS连第一层都完不了。加数个数需要限制，并且必须剪枝。

每多一层，相当于多一个加数。迭代加深搜索逐步加深 maxd，直接能满足加数越少越好的条件。

类似子集的增量构造，分母从小到大地搜索。

乐观估计剪枝与IDA#

算法最初要算出能选择的最小分母，从而从此开始一个一个试。每次选择新加数的分母，都应该大于现有的所有分母。
如果选择到某一层的时候，最小能选择到 a，最大的情况（实际达不到）是后面所有层都选择 a，如果这样最后的和还小于所求，则可以直接剪枝掉这个maxd，直接maxd++再搜索。
这里比较特殊，可以直接剪枝整个maxd。

乐观估计本质是放缩。乐观估计+剪枝的技巧决定了回溯法（或IDA）能在无限尺度上运行。

状态空间搜索与BFS#

把一个状态看做图中的一个节点，通过某些规定的操作这个状态能变成下几个后继状态，这些后继状态相当于有向图中原状态节点能够达到的边，并且没有边权。这时候最短步骤问题可以转化为BFS的最短路径。这称为隐式图。

八数码问题是经典的状态空间搜索。

有时候状态空间搜索会带上“边”权重，这就需要 Dijkstra 。

倒水问题
容积为abc的三个容器，没有刻度，初始时有已知体积的水在其中，问最少倒水量的方案，使某个容器中出现 k 体积的水（往外倒）？

三个容器中水体积是状态。每个状态的后继数量是有限的（最多6种倒法）。不过问题问的是最少倒水量，所以边有权重，即倒水量。这里需要 Dijkstra 出马。
如果问的是最小步骤数，则没有边权，可以直接BFS。

判重#

不管是 BFS 还是 Dijkstra 都有判重的步骤，判断“新”层是否已经在队列中，这里有三个技巧：

• 编码、解码，即完美哈希

• 哈希，可能冲突。

• STL set。