AcWing 94. 递归实现排列型枚举DFS递归

一、题目链接

AcWing 94. 递归实现排列型枚举

二、题目分析

（一）算法标签

DFS 递归

（二）解题思路

详细了解搜索类题目(DFS、BFS)，请移步DFS BFS 搜索题目归纳

三、AC代码

解法一:

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 10;

int n;
int state[N];   // 0表示没放数, 1~n表示放了哪个数
bool used[N];   // 1~n 哪个数被用了

void dfs(int u)
{
    if (u > n)
    {
        for (int i = 1; i <= n; i    )
        {
            printf("%d ", state[i]);
        }
        puts("");
    }
    
    for (int i = 1; i <= n; i    )
    {
        if (!used[i])
        {
            state[u] = i;
            used[i] = true;
            dfs(u   1);
            state[u] = 0;
            used[i] = false;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    return 0;
}

vector存下方案：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

vector<vector<int>> ways;

int state[N];
bool st[N];
int n;

void dfs(int u)
{
    if (u > n)
    {
        vector<int> way;
        for (int i = 1; i <= n; i    )
            way.push_back(state[i]);
        ways.push_back(way);
        return;
    }
    
    for (int i = 1; i <= n; i    )
    {
        if (!st[i])
        {
            state[u] = i;
            st[i] = true;
            dfs(u   1);
            st[i] = false;
            state[u] = 0;
        }
    }
}
int main()
{
    cin >> n;
    dfs(1);
    
    for (int i = 0; i < ways.size(); i    )
    {
        for (int j = 0; j < ways[i].size(); j    )
            printf("%d ", ways[i][j]);
        puts("");
    }
    return 0;
}

四、其它题解

AcWing 94. 递归实现排列型枚举

这篇好文章是转载于：学新通技术网