排列组合类DFS暴力搜索

排列与组合是最经典的DFS暴力搜索题型，本质都是「从n个元素中按规则选出若干个」。排列：在乎顺序，如123的排列有六种。组合：不在乎顺序，如123的组合就这一种。
如果用循环实现，全排列需要写n层循环，组合需要写k层循环，元素数量变化时代码无法复用。而递归可以通过depth参数动态控制循环层数，完美解决这个问题。

这类题目的核心三要素：

1. depth参数：控制当前递归层数，也就是已经选了多少个元素
2. 防重复机制：排列用vis数组，组合用last参数
3. 回溯操作：选入元素递归返回后，必须手动撤销选择，恢复现场

一、排列问题：P1706 全排列问题

问题重述

给定正整数 n，输出 1∼n 所有的全排列，按字典序输出，每个数字占 5 个字符宽度。

输入样例：

3

输出样例：

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

核心思路

全排列相当于写 n 层嵌套循环，每层选一个数，且不能和前面选过的重复。当 n 很大时，手写多层循环不现实，用递归的 depth 参数替代循环层数，每层递归完成一次选数操作。

DFS参数设计

• depth：当前递归层数，表示已经选好了 depth-1 个数，正在选第 depth 个
• vis[]：布尔数组，标记某个数字是否已经被选中
• vector<int> res：存储当前已经选出的排列

防重复原理：vis标记数组

排列中每个数字只能使用一次，因此每次选数前必须检查该数字是否已被使用：

• 若未被使用（vis[i] == false），则可以选择它，标记为已使用，加入当前排列
• 递归返回后，取消标记，让其他分支可以再次选择这个数字

为什么需要回溯

res 是所有递归分支共用的容器。如果选入元素后不撤销，递归返回上一层时，这个元素会残留在 res 中，污染后续的分支选择。

例如选完 1→2→3 返回后，必须先把 3 弹出，才能继续尝试选其他数字作为第三位；如果不弹出，下一次选数会直接接在 3 后面，得到错误的排列。
vis数组同理，若不取消标记，后续分支就无法再使用这个数字。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 10;
int n;
bool vis[N];
vector<int> res;

void dfs(int depth) {
    // 边界：选满n个数，输出结果
    if (depth == n + 1) {
        for (int x : res) {
            cout << setw(5) << x;
        }
        cout << endl;
        return;
    }
    // 遍历所有可选数字
    for (int i = 1; i <= n; i++) {
        if (!vis[i]) {
            // 做出选择：标记 + 加入结果
            vis[i] = true;
            res.push_back(i);
            // 递归下一层
            dfs(depth + 1);
            // 回溯：撤销标记 + 弹出元素
            res.pop_back();
            vis[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs(1);
    return 0;
}

二、组合问题：P1157 组合的输出

问题重述

给定正整数 n 和 r，输出从 1∼n 中选 r 个数的所有组合，按字典序输出，每个数字占 3 个字符宽度。

输入样例：

5 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

组合与排列的核心区别

组合不考虑元素顺序，{1,2} 和 {2,1} 是同一个组合。如果沿用排列的vis数组写法，会生成大量重复组合。

解决方案是强制升序选择：每次只能选比上一个数更大的数，保证每个组合只会按从小到大的顺序生成一次，天然去重。

防重复原理：last参数限制范围

用 last 参数记录上一个选中的数字，当前层只能从 last + 1 开始选数：

• 第一层可以从 1 开始选
• 第二层只能从第一层选的数 + 1 开始选
• 以此类推，最终组合必然是升序的，不会出现重复

这种方式不需要vis数组，通过范围限制天然保证每个元素最多选一次。

DFS参数设计

• depth：当前递归层数，正在选第 depth 个数
• last：上一个选中的数字，限制当前可选范围
• vector<int> res：存储当前组合

回溯操作

和排列同理，res 是共享容器，递归返回后必须弹出最后加入的元素，恢复现场，以便尝试同层的下一个可选数字。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int N = 25;
int n, r;
vector<int> res;

void dfs(int depth, int last) {
    // 边界：选满r个数，输出结果
    if (depth == r + 1) {
        for (int x : res) {
            cout << setw(3) << x;
        }
        cout << endl;
        return;
    }
    // 只能从last+1开始选，保证升序不重复
    for (int i = last + 1; i <= n; i++) {
        res.push_back(i);
        dfs(depth + 1, i);
        res.pop_back(); // 回溯
    }
}

int main() {
    cin >> n >> r;
    dfs(1, 0); // 第一层从0的下一个，也就是1开始选
    return 0;
}

三、核心概念总结

1. 两种防重复机制对比

2. 回溯的本质

回溯的核心是恢复现场。由于我们用同一个容器（vector）、同一份标记数组存储当前选择路径，所有递归分支共享这一份数据。当一条分支遍历完毕返回时，必须撤销这条分支做出的选择，否则会叠加到后续其他分支的状态，导致结果错误。

不仅是vector和vis数组，后续DFS题目中的状态回退，本质都是回溯思想。