题目描述

给定一个整数 n，将数字 1∼n排成一排，将会有很多种排列方法。
现在，请你按照字典序将所有的排列方法输出。

输入格式

共一行，包含一个整数 n。

输出格式

按字典序输出所有排列方案，每个方案占一行

解题思路

毫不犹豫选择了新玩意儿:深度搜索树,但是作为小白总是会有一股奇妙的熟悉感:动态规划
这两个还是有不同滴,虽然它们都可以记录节点,简化时间复杂度,但是一个适用于树状图,一个适合优化
还有就是深度搜索是从中心发散,而动态规划是从远端到近端生成

好,进入正题,深度搜索树要有三个东西:树根,树干,树叶(bushi)->节点(数据),层数,标记(优化用)
首先定义一个节点数组储存数字,然后定义一个jugde数组用于判断,同时u表示树的层数
声明myFunction还有层数u,自定义函数有一个习惯先写结果再出过程,如果u==n,也就是到达最后一层,输出即可
过程就是首先for循环控制遍历所有数据元素,然后if条件句判断该元素有无标记
如果没有标记则放入节点库,同时标记为使用过(true),通过再次调用函数递归进入下一层再换标记为未使用(false)
全程无运算,主打的就是一个标记和输出

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

int point[10];
bool judge[10];
int n;

void myFunction(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<point[i]<<" ";
        }
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++){
        if(!judge[i]){
            point[u]=i;
            judge[i]=true;
            myFunction(u+1);
            judge[i]=false;
        }
    }
}
int main(){
    cin>>n;
    myFunction(0);
    return 0;
}

篇章

上一篇:AcWing 822. 走方格
https://www.acwing.com/solution/content/211675/
下一篇:AcWing 21. 斐波那契数列(迭代)
https://www.acwing.com/solution/content/211756/