暴力枚举

前置知识

递归思想、递归代码框架

目标

Complete Search

枚举子集、枚举组合、枚举排列的代码模板

Complete Search

Complete search is a general method that can be used to solve almost any algorithm problem.

The idea is to generate all possible solutions to the problem using brute force, and then select the best solution or count the number of solutions, depending on the problem.

Complete search is a good technique if there is enough time to go through all the solutions, because the search is usually easy to implement and it always gives the correct answer.

If complete search is too slow, other techniques, such as greedy algorithms or dynamic programming, may be needed.

递归实现指数型枚举

\(2^n\)

vector<int> chosen;

void dfs(int u) {
    if (u == n + 1) {   //也可以写 u > n
        for (auto i : chosen) cout << a[i] << ' '; // 输出时，套一下数组的值
        cout << endl;

        return ;
    }

    // 先 不选第u个元素，还是先 选第u个元素。
    // 会影响我们的输出顺序

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

    //选u
    chosen.push_back(u);
    dfs(u + 1);
    chosen.pop_back();  //回溯，恢复现场
}

//拓展，位运算版本，这是进阶的
void dfs(int u, int state) {
    if (u == n) {
        for (int i = 0; i < n; i++)
            if (state >> i & 1) cout << a[i + 1] << ' ';  // 输出时，套一下数组的值
        cout << endl;

        return ;
    }

    //求解子问题
    dfs(u + 1, state);          //不选，state初始是0，等价于dfs(u + 1, state & (~(1 << u)));
    dfs(u + 1, state | 1 << u); //选
}

递归实现组合型枚举

\(C^m_n\)

vector<int> chosen;

void dfs(int u) {
    if (chosen.size() > m || chosen.size() + (n - u + 1) < m) return ;

    if (u == n + 1) {
        for (auto i : chosen) cout << a[i] << ' '; // 输出时，套一下数组的值
        cout << endl;

        return ;
    }

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

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

//拓展，递归实现，枚举的时候带着顺序
void get_combination(int u, int last) {
    if (u == m) {
        for (int i = 0; i < m; i++) printf("%d ", chosen[i]);
        puts("");
    }

    for (int j = last + 1; j <= n; j++){
        chosen.push_back(j);
        get_combination(u + 1, j);
        chosen.pop_back();
    }
}

//拓展，位运算版本，这是进阶的
//state表示状态
void dfs(int u, int sum, int state) {
    if (sum > m || sum + n - u < m) return ;

    if (sum == m) {
        for (int i = 0; i < n; i++)
            if (state >> i & 1) cout << a[i + 1] << ' '; // // 输出时，套一下数组的值
        cout << endl;

        return ;
    }

    dfs(u + 1, sum + 1, state | 1 << u);
    dfs(u + 1, sum    , state         );
}

递归实现排列型枚举

\(n!\)

//用数组存方案
//注意一下 0-index(如果是 1-index 呢)
//递归的边界是....什么？(提问)

void dfs(int u) {
    if (u == n) {
        for (int i = 0; i < n; i++) cout << order[i] << ' ';
        puts("");
    }

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

        order[u] = i;
        chosen[i] = true;
        dfs(u + 1);
        chosen[i] = false;
    }
}

//拓展，用vector来存方案，用二进制数来记录状态
vector<int> path;
void dfs(int u, int state) {
    if (u == n) {
        vector<int>::iterator i;
        for (i = path.begin(); i < path.end(); i++)
            cout << *i << ' ';
        puts("");
    }

    for (int i = 0; i < n; i++)
        if (!(state >> i & 1)) {
            path.push_back(i + 1);   //用vector来记录方案
            dfs(u + 1, state | 1 << i);
            path.pop_back();
        }
}

总结

递归枚举子集/组合/全排列，需要非常熟练