深度优先搜索I
# 背景
宽度优先（BFS）是一圈一圈向外摸，深度优先（DFS）则是一条路走到黑，走到无论可走时，再退回去走其它的路。
# 枚举问题
请列出用数字1，2，3（每个数字可以用无数个）组成的三位数。 这个问题确定是三位数，我们可以直接三层for循环来处理。
for (int i = 1; i <= 3; i++) {
for (int j = 1; j <= 3; j++) {
for (int k = 1; k <= 3; k++) {
cout << i << j << k << endl;
}
}
}
2
3
4
5
6
7
问题进化一下：请列出用数字1，2，3（每个数字可以用无数个）组成的n位数。 我们发现3位数3层for循环，n是一个读入的变量，这没法用for循环实现了。
我们用dfs来处理枚举
#include <bits/stdc++.h>
using namespace std;
int n;
int a[5];
void dfs(int x) { // 当前枚举的是第x位
if (x == n + 1) { // 递归出口，一共n个位置要考虑，当x等于n+1时，前n个位置都处理完
for (int i = 1; i <= 3; i++) { // 打印当前的三位数
cout << i;
}
cout << endl;
return;
}
for (int i = 1; i <= 3; i++) { // 第x位有三种选择1，2，3
a[x] = i; // 将第x位选择的值记录在a数组中
dfs(x + 1); // 递归到下一个位置去处理
}
}
int main() {
cin >> n;
dfs(1); // 从第一位开始枚举
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
我们发现递归函数中有一个x变量，用它来控制递归的进行。 递归的出口就是该变量的一个限制条件。 这也是我们看到的DFS的第一种应用，处理枚举问题，模拟for循环。
# 排列问题
给定一个正整数n(n < 10)，输出1->n的全排列，要求从小到大。 在全排列中，每个数只能使用1次。
#include <bits/stdc++.h>
using namespace std;
int n;
int a[15];
bool v[15]; // 记录一个数是否被使用过，默认false。
void dfs(int x) {
if (x == n + 1) {
for (int i = 1; i <= n; i++) {
cout << a[i];
}
cout << endl;
return;
}
for (int i = 1; i <= n; i++) {
if (v[i]) { // 如果i已经被使用，跳过该情况
continue;
}
v[i] = true; // 第x个数使用了i，做好标记
a[x] = i; // 记录第x个数的选择：i
dfs(x + 1); // 继续去选下一个数
v[i] = false; // 数i被释放，可供后续情况选用
}
}
int main(void) {
cin >> n;
dfs(1); // 从全排列的第一位开始枚举
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
这类问题叫做回溯问题，写法非常像汉堡包，或者可以理解成，进去关门，出来开门，用完释放资源的感觉。 经典的回溯问题还有n皇后问题，一个皇后占掉的行和列还有对角线，下一个皇后就不能放了。
排列问题也可以使用库函数next_permutation解决：
#include <bits/stdc++.h>
using namespace std;
int a[15];
int main(void) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) { // 初始化a数组中为1->n的最小排列
a[i] = i;
}
do {
for (int i = 1; i <= n; i++) {
cout << a[i];
}
cout << endl;
} while (next_permutation(a + 1, a + 1 + n)); // 当下一个排列不存在时，返回false，循环结束。
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
注意：角标从1开始使用，所以next_permutation的第一个参数给了a+1。
# 组合问题
给出在1->n(n<10)中挑k个数的组合。从小到大输出。 123和132是一种组合。 我们只要保证每一种给出的组合是字典序从大到小排好序的即可。
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[15];
void dfs(int start, int x) { // 加一个start，表示当前位置，只可以从start开始选数。
if (x == k + 1) {
for (int i = 1; i <= k; i++) {
cout << a[i];
}
cout << endl;
return;
}
for (int i = start; i <= n; i++) { // 从start开始遍历，保证结果升序
a[x] = i;
dfs(i + 1, x + 1); // 当前选了i，下一次只能从i+1开始选
}
}
int main(void) {
cin >> n >> k;
dfs(1, 1);
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
我们通过start变量保证了无重复，如果上一次选了3，下一次只能从4开始选。 所有结果都是升序的，自然就不会出现123与132(不是升序)这样的重复了。
其实组合问题，还可以用二进制来枚举
C B A
0 0 0 => 0
0 0 1 => 1
0 1 0 => 2
0 1 1 => 3
1 0 0 => 4
1 0 1 => 5
1 1 0 => 6
1 1 1 => 7
2
3
4
5
6
7
8
9
三个数选与不选对应的所有情况，正好可以用整数0->7来完全表示出来。如果说3选2，那我们就取所有二进制表示中有2个1的情况就可以了。
#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[15];
int main(void) {
cin >> n >> k;
int U = 1 << n; // 2的n次方
for (int i = 0; i < U; i++) {
if (__builtin_popcount(i) == k) {
for (int j = 0; j < n; j++) { // 从最低位开始
if (i & (1 << j)) cout << j + 1; // 由于我们从1开始，第0位表示1
}
cout << endl;
}
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
二进制枚举效率比较高，在子集问题中，可以考虑使用。