课堂笔记：深度优先搜索（DFS）解决组合与全排列问题

一、组合问题：从 $n$ 个元素中选 $r$ 个

1. 题目回顾

• 输入：两个自然数 $n, r$（$1 < n < 21$，$1 \leq r \leq n$）。
• 输出：从 $1 \sim n$ 中选出 $r$ 个数的所有组合，按字典序且元素递增排列。

2. 算法思路

组合的核心是“无序且不重复”，因此通过保证每次选的数比上一个大（用 pre 记录上一个数），避免重复组合（如 1,2 和 2,1 视为同一组合，仅保留 1,2）。

使用 DFS 递归构建组合：

• step：记录已选数字的个数；
• pre：记录上一次选的数字，确保下次从 pre+1 开始选；
• vector<int> v：存储当前已选的数字。

3. 代码详解

#include<bits/stdc++.h>
using namespace std;
int n, k;  // n是总元素数，k是要选的元素数（即题目中的r）

// step：已选数字个数；pre：上一次选的数字；v：当前已选数字的容器
void dfs(int step, int pre, vector<int> v) {
    // 递归终止条件：已选满k个数字，输出组合
    if (step == k) {
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;
        return;
    }
    // 从pre+1开始选，保证数字递增
    for (int i = pre + 1; i <= n; i++) {
        vector<int> v2 = v;  // 复制当前已选数字
        v2.push_back(i);     // 加入当前选的数字i
        dfs(step + 1, i, v2);  // 递归：已选数+1，更新pre为i
    }
}

int main() {
    cin >> n >> k;
    vector<int> v;
    dfs(0, 0, v);  // 初始：已选0个，上一个数是0，空容器
    return 0;
}

4. 关键注意事项

• 递增保证：通过 pre 限制下一个数从 pre+1 开始，避免重复组合；
• 容器复制：每次递归时复制 vector（v2 = v），无需额外回溯（因为不同分支的容器独立）。

二、全排列问题：$n$ 个不同元素的全排列

1. 题目回顾

• 输入：第1行是整数 $n$（$1 \leq n \leq 8$）；第2行是 $n$ 个互不相等的整数（$1 \leq$ 数值 $\leq 9$）。
• 输出：所有全排列，按字典序排列。

2. 算法思路

全排列的核心是“有序且不重复选同一元素”，因此：

• 先对输入数组排序，保证输出的排列按字典序；
• 用 vis 数组标记每个位置是否已被选过；
• 回溯：递归返回后取消标记（vis[i] = 0），让其他分支可以使用该元素。

3. 代码详解

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int n, a[N], vis[N];  // a存输入数字，vis标记是否选过

// step：当前排列的长度；v：存已选元素的下标（对应a数组）
void dfs(int step, vector<int> v) {
    // 递归终止条件：排列长度为n，输出排列
    if (step == n) {
        for (int i = 0; i < v.size(); i++) {
            cout << a[v[i]] << " ";  // 通过下标访问a数组（已排序）
        }
        cout << endl;
        return;
    }
    // 遍历所有位置（1~n，数组下标从1开始）
    for (int i = 1; i <= n; i++) {
        if (vis[i] == 0) {  // 若第i个位置未被选过
            vis[i] = 1;      // 标记为已选
            vector<int> v2 = v;
            v2.push_back(i); // 存下标i（不是a[i]，因为要保证字典序）
            dfs(step + 1, v2);  // 递归：排列长度+1
            vis[i] = 0;      // 回溯：取消标记，让其他分支使用
        }
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);  // 先排序，保证字典序
    vector<int> v;
    dfs(0, v);  // 初始：排列长度0，空容器
    return 0;
}

4. 关键注意事项

• 排序保证字典序：先对 a 数组排序，后续通过下标访问即可保证输出有序；
• vis 数组的回溯：递归返回后必须 vis[i] = 0，否则同一元素无法在其他分支中被选中；
• 存下标而非数值：v 中存储的是 a 数组的下标（i），而非 a[i]，确保排序后的顺序被严格遵循。

三、组合与全排列的核心对比

四、代码优化建议

1. 组合问题的引用传递优化： 原代码中每次复制 vector 效率较低，可改为引用传递 + 回溯：

   void dfs(int step, int pre, vector<int>& v) {  // 引用传递
       if (step == k) { /* 输出 */ return; }
       for (int i = pre + 1; i <= n; i++) {
           v.push_back(i);
           dfs(step + 1, i, v);
           v.pop_back();  // 回溯：删除最后一个元素
       }
   }
   

2. 数组下标一致性： 全排列代码中 a 数组从 1 开始存储，是为了方便 vis 数组的标记（i 从 1 到 n），初学者可根据习惯调整为从 0 开始，但需注意循环范围和标记逻辑的统一。