洛谷题单指南-暴力枚举-P1706 全排列问题

原题链接：https://www.luogu.com.cn/problem/P1706

题意解读：n个数全排列问题，本质上，给定n个空位，枚举每个能填入空位的数，依次填入，每个数只能填一次。

解题思路：

如何填入n个数呢，可以借助于递归，流程如下：

dfs(填入第k个数)
{
    如果已经填满n个数
        输出结果
        返回
    枚举从1到n的数
        如果当前数没有填过
            填入第k个数
            记录已填入的数已被使用
            dfs(填入第k+1个数)
            释放已填入的数以便回溯
}

下面图示给出递归填数的过程：

最后，给出对应代码

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

const int N = 15;

int n;
int t[N]; //用来存储1-n个数的一次排列
bool flag[N];

//每次填第k个数
void dfs(int k)
{
    if(k > n) //如果已填满n个数，输出结果
    {
        for(int i = 1; i <= n; i++)
        {
            cout << setw(5) << t[i];
        }
        cout << endl;
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!flag[i]) //如果i没有填过
        { 
            flag[i] = true; //记录i已填
            t[k] = i; //第k个数填i
            dfs(k + 1); //继续填第k + 1个数
            flag[i] = false; //恢复i已填标记，便于回溯
        }  
    }
}

int main()
{
    cin >> n;

    dfs(1);

    return 0;
}

递归调用的顺序如图中红色箭头所示：