题目描述

blablabla

样例

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

using namespace std;

const int N = 10;

int n;

void dfs(int u, int nums[], bool st[])//u表示当前要填充的位置，nums存储当前的排列， st用来跟踪那些数字已被使用
{
    if(u>n)//当u超过n时表示当前的排列已经完整，将结果输出
    {
        for(int i=1; i<=n; i++) cout << nums[i] << ' ';
        cout << endl;
    }
    else
    {
        for(int i = 1;i<=n; i++)
            if(!st[i])
            {
                st[i] = true;//标记数字i为已使用
                nums[u] = i;//将当前数字i填充到当前位置
                dfs(u+1, nums, st);//递归调用，填充下一个位置
                st[i] = false;//恢复现场
            }//使用深度优先搜索的方法来生成1-n的所有排列
                // 每次递归尝试将一个未被使用过的数字填入排列中，直到达到一个基准情况
                // 使用st数组来记录数字的使用情况，并在递归结束后恢复状态，为下一个排列的生成做好准备

    }
}

int main()
{
    cin >> n;
    int nums[N];
    bool st[N] = {0};

    dfs(1, nums, st);

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla