Solves

Appearance

递归实现指数型枚举 ​

从 1∼n 这 n(n<20) 个整数中随机选取任意多个，输出所有可能的选择方案。

分析 ​

每个整数都有可选可不选两种情况，总的方案数为 2n，通过前面所讲的二进制子集枚举，我们可以使用一次循环求解。而本节我们使用递归求解，在递归中分别尝试某个数是选了还是没选，从而将问题分解为更小的子问题。

代码 ​

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

vector<int> v;
int n;

void dfs(int u) {
    if (u == n + 1) {
        for (auto x : v) {
            cout << x << " ";
        }
        cout << endl;
        return ;
    }

    // 不选
    dfs(u + 1);

    // 选
    v.push_back(u);
    dfs(u + 1);
    v.pop_back();
}

int main() {
    cin >> n;

    dfs(1);

    return 0;
}

递归实现组合型枚举 ​

从 1∼n 这 n 个整数中随机选取 m(0≤m≤n<20) 个，输出所有可能的选择方案。

分析 ​

我们只需要在递归函数的开头加上下面这行代码即可：

cpp
if (v.size() > m || v.size() + (n - u + 1) < m) return ;

这就是所谓的剪枝！如果已经选择了超过 m 个数，或者即使再选上剩余的 n−u+1 个数也不够 m 个，那么就不用继续递归了（无解）。

代码 ​

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

vector<int> v;
int n, m;

void dfs(int u) {
    if (v.size() > m || v.size() + (n - u + 1) < m) return ;
    if (u == n + 1) {
        for (auto x : v) {
            cout << x << " ";
        }
        cout << endl;
        return ;
    }

    // 选
    v.push_back(u);
    dfs(u + 1);
    v.pop_back();

    // 不选
    dfs(u + 1);
}

int main() {
    cin >> n >> m;

    dfs(1);

    return 0;
}

递归实现排列型枚举 ​

把 1∼n 这 n 个整数排成一行后随机打乱顺序，输出所有可能的排列方案。

分析 ​

这就是全排列问题，所有可能的方案总数为 n!，我们可以在递归中尝试每个数放在当前的位置上，然后继续递归求解剩余位置的方案。

代码 ​

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

int n, vis[20];
vector<int> v;

void dfs(int u) {
    if (u == n + 1) {
        for (int i = 0; i < v.size(); i++) {
            cout << v[i] << " ";
        }
        cout << endl;

        return ;
    }

    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;

        vis[i] = 1;
        v.push_back(i);
        dfs(u + 1);
        v.pop_back();
        vis[i] = 0;
    }
}

int main() {
    cin >> n;

    dfs(1);

    return 0;
}

思考：如果是从 n 个整数中选出 m 个数进行全排列呢？

习题 ​

Copyright © 2025-present loop3r