暴力枚举

前置知识

递归思想、递归代码框架

目标

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.

递归实现指数型枚举

vector<int> chosen;

void dfs(int x)
{
    if (x == n + 1)   //也可以写x > n
    {
        for (int i = 0; i < chosen.size(); i++)
            printf("%d ", chosen[i]);
        puts("");

        return ;
    }

    //问：先不选x， 还是先选x。会影响我们的输出顺序
    //观察样例，我们先不选x

    //不选x，求解子问题
    dfs(x + 1);

    //选x，求解子问题
    chosen.push_back(x);
    dfs(x + 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 << i + 1 << ' ';
        puts("");

        return ;
    }

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

递归实现组合型枚举

vector<int> chosen;

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

    if (x == n + 1)
    {
        //如何输出状态
        for (int i = 0; i < chosen.size(); i++)
            printf("%d ", chosen[i]);
        puts("");

        return ;
    }

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

    //不选x
    dfs(x + 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 << i + 1 << ' ';
        puts("");

        return ;
    }

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

递归实现排列型枚举

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

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

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

        order[k] = i;
        chosen[i] = true;
        dfs(k + 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();
        }
}

总结

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