AcWing | 【DFS】排列数字

た入场券 2022-12-20 06:00 168阅读 0赞

**题目内容**

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

**输入格式**

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

**输出格式**

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

**数据范围**

> 1≤n≤7

**输入样例：**

3

**输出样例：**

1 2 3
    1 3 2
    2 1 3
    2 3 1
    3 1 2
    3 2 1

--------------------

**思路：**

*  题目要求输出数组的全排列，核心是考虑清楚以什么样的顺序搜索最方便：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]
 *  注意需要回溯，以保证下一次搜的时候是按最原始的时候搜的。

**完整代码：**

#include<iostream>
    using namespace std;
    const int N=10;
    int n;
    int path[N];//用来存路径
    bool st[N];//用来存状态 是否被用过
    void dfs(int u){ 
        if(u==n){ //如果已经全部遍历完了 就直接输出路径即可，u相当于树的层数
            for(int i=0;i<n;i++)printf("%d ",path[i]);
            puts(" ");
            return;
        }
        for(int i=1;i<=n;i++){ 
            if(!st[i]){ //如果i没被用过 就用一下他
                path[u]=i;//把路径记录下来
                st[i]=true;//修改状态表示已经被用过了
                dfs(u+1);//递归下一位
                st[i]=false;//回溯 恢复现场
            }
        }
    }
    int main(){ 
        cin>>n;
        dfs(0);
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMTQ1OTI2_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/5d3e0b0535ed4b0792a5336ee0f4a3e1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，168人围观）

还没有评论，来说两句吧...

相关阅读

相关双向DFS AcWing 171. 送礼物

双向DFS AcWing 171. 送礼物原题链接 [AcWing 171. 送礼物][AcWing 171.] 算法标签搜索双向搜索思路

迈不过友情╰/ 2024年04月07日 11:54/ 0 赞/ 83 阅读

相关全排列深搜dfs

include<iostream> include<cstdio> using namespace std; int a[100],vis[10

- 日理万妓/ 2024年02月17日 19:26/ 0 赞/ 84 阅读

相关打印全排列（DFS）

> 前言：OJ上一道简单算法题，打印全排列。用深度优先搜索（DFS）来实现，顺便记录一下基础DFS模板。题目描述给定一个正整数n，取出前n小的正整数，即 1~n 这

超、凢脫俗/ 2023年03月01日 08:38/ 0 赞/ 112 阅读

相关 AcWing 1113. 红与黑（BFS、DFS）

上一篇博客：[LeetCode 4. 寻找两个正序数组的中位数][LeetCode 4.] > 写在前面：大家好！我是`AC-fun`,我的昵称来自两个单词`Accepte

末蓝、/ 2023年01月06日 14:54/ 0 赞/ 178 阅读

相关 AcWing | 【DFS】n-皇后问题

题目内容： > n-皇后问题是指将 n 个皇后放在 n∗n的国际象棋棋盘上，使得皇后不能相互攻击到，即任意两个皇后都不能处于同一行、同一列或同一斜线上。现在给定整数n，请你输

男娘i/ 2022年12月20日 11:23/ 0 赞/ 203 阅读

相关 AcWing | 【DFS】排列数字

题目内容 > 给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。 > > 现在，请你按照字典序将所有的排列方法输出。输入格式 > 共一行，包含一个整数n。

た入场券/ 2022年12月20日 06:00/ 0 赞/ 169 阅读

相关全排列——回溯算法+dfs

leetcode.46.全排列——回溯算法+dfs 给定一个没有重复数字的序列，返回其所有可能的全排列。示例: 输入: [1,2,3] 输出:

骑猪看日落/ 2022年12月04日 15:56/ 0 赞/ 255 阅读

相关 526. 优美的排列(dfs)

假设有从 1 到 N 的 N 个整数，如果从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 满足如下两个条件中的一个，我们就称这个数组为一

Love The Way You Lie/ 2022年09月05日 01:56/ 0 赞/ 198 阅读

相关补全等式(DFS,全排列)

下图中，每个方块代表 1…13 中的某一个数字，但不重复。 ![这里写图片描述][SouthEast] 例如： 1×2+9×7=13×5 10×8+12×3=1

迈不过友情╰/ 2022年06月18日 09:14/ 0 赞/ 253 阅读

相关数字排列

输入M、N，显示数字排列，如输入４、６： 1 3 6 10 14 18 2 5 9 13 17 21 4 8 12 16 20

末蓝、/ 2022年05月31日 05:49/ 0 赞/ 213 阅读