··前言：

DFS作为蓝桥杯等大赛的必备算法，是必须要掌握和学会灵活应用的

··问题形象化（图片来自《啊哈！算法》）：

假如有编号为1、2、3的3张扑克牌和编号为1、2、3的3个盒子，现在我们想把这3张扑克牌分别放进3个盒子里面，并且每个盒子有且只能放一张扑克牌，那么一共有多少中不同的方法？

首先，我们手拿三张扑克牌，走到了1号盒子前，我们心想：放1号扑克牌，还是2号、3号呢？现在我们想生成全排列，所以肯定要将三种情况全部尝试一次。那么现在我们约定一个顺序，每次到一个盒子面前，都先放1号，再放2号，最后放3号，所以我们现在把1号扑克牌放进第一个盒子中
放好之后，我们走到第二个盒子面前，现在手里剩下2、3号，按照以前的约定顺序，我们将2号扑克牌放进2号盒子中，接着我们来到3号盒子面前
现在我们手上只剩下3号扑克牌了，于是只能将手中的3号放入其中，放好后，我们再往后走一步，走到了第4号盒子（实际上没有），这时我们手中已经没有扑克牌了，现在，观察前三个盒子，成功的生成了一组全排列，即“1 2 3”.
但是我们不可能由此结束，我们还要回到3号盒子面前，收回3号扑克牌，但是因为我们手中除了3号已经没有其他扑克牌了，所以我们还要往前走一个箱子，来到了2号前。
我们收回2号扑克牌，现在，我们手中有2、3号扑克牌了，按照约定的顺序，我们把3号扑克牌放入其中，放完后我们再次向后走一步，来到3号箱子前。
此时我们手中只剩下2号扑克牌了，我们将2号扑克牌放进3号箱子中，放完后向后走一部，来到第4号盒子前（实际上没有）
此时，我们再次成功的生成了一组排列，即“1 3 2”.
我们如果多次重复上面的步骤，先返回到3号，取回2号卡片，再返回到2号，取回3号，再返回到1号，取回1号，再前进放入，再返回。。。。如此往复，我们可以生成所有的排列可能。
由此我们可以写出如下代码

#include<stdio.h>
int box[20 + 5], book[20 + 5],n;//box是箱子，book用于储存是否卡牌被使用
void dfs(int step);
int main() {
	//实现1~n的全排列
	scanf("%d", &n);
	dfs(1);
	return 0;
}
void dfs(int step) {
	if (step == n + 1) {//临界条件，此时我们已经走到了第n+1个盒子前
		int i;
		printf("%d", box[1]);
		for (i = 2; i <= n; i++) {
			printf(" %d", box[i]);
		}
		printf("\n");
		return;
	}
	//现在站在第step个箱子前
	int i;
	for (i = 1; i <= n; i++) {//逐个遍历每张卡片
		if (book[i] == 0) {//如果这张卡片没有被使用过
			box[step] = i;
			book[i] = 1;
			dfs(step + 1);
			book[i] = 0;//递归放完卡片之后，要将卡片恢复为未使用状态，以便后续操作
		}
	}
	return;
}

下面我们分析一道变式题目：
【递归入门】组合的输出
[命题人 : 外部导入]
时间限制 : 1.000 sec 内存限制 : 128 MB

解决: 728
提交: 728
统计
题目描述
排列与组合是常用的数学方法，其中组合就是从n个元素中抽出r个元素(不分顺序且r < ＝ n)，我们可以简单地将n个元素理解为自然数1，2，…，n，从中任取r个数。
现要求你不用递归的方法输出所有组合。
例如n ＝ 5 ，r ＝ 3 ，所有组合为：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
输入
一行两个自然数n、r ( 1 < n < 21，1 < ＝ r < ＝ n )。
输出
所有的组合，每一个组合占一行且其中的元素按由小到大的顺序排列，所有的组合也按字典顺序。

问题分析：这道题目和上面例题的不同之处在于，该题要求从n个数中取出r个数，而不是n个数的全排列，并且还有一个要点，在于输出的元素按由小到大排列，所有的组合还要按照字典顺序

#include<iostream>
using namespace std;
int a[21+5], b[21+5] = { 0 }, n, r;//a是箱子，b是信号量判断是否已经被使用
void dfs(int step) {
    int i, j;
    if (step == r + 1) {//只允许放r个盒子，step>r就结束放盒子，开始输出r个数据
        for (i = 1; i <= r; i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }
    for (i = a[step - 1]; i <= n; i++) {//i每次都以前一个盒子里数为开端开始遍历，这样避免从1开始遍历，导致后面盒子的数比前面盒子的数小
        if (b[i] == 0) {
            b[i] = 1;
            a[step] = i;
            dfs(step + 1);
            b[i] = 0;
        }
    }
    return;
}
int main() {
    scanf("%d%d", &n, &r);
    a[0] = 1;//配合上面的a[step-1]，初次要从1号卡牌开始遍历
    dfs(1);
    return 0;
}

两个关键点阐释：

1.对于i=a[step-1]的理解
我的观点如下：
假设有5个数，要取出3个数组成全排列，第一次进入循环，肯定是按照1、2、3的顺序放进盒子，待返回时，取出3，这时比3大的有4、5，将4放进去，取出来，放入5，再返回到2号前，放入3.。。。对于这一趟循环，肯定时满足从小到大的。但是如果我们走到1号盒子前，把1号卡牌取出，紧接着把2号放进去，下一步走到2号盒子前，假设i还是从1开始的，我们会把1号卡牌放进去，这样就违背了从小到大的原则了，所以我们应该是从3开始，保证箱子里的数字从左到右都是从小到大排列的。
2. 如何保证是只输出r个，组成一次排列
这里我们只安排r个盒子就可以了，r个盒子一旦装满，即step=r+1，我们就可以输出当前序列了。因此正确做法是修改临界条件