首页 > 试题广场 >

全排列

[编程题]全排列
  • 热度指数：2004 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
{\hspace{15pt}}给定一个整数 n，请按 字典序 输出数字 1\sim n 的所有排列。

输入描述:
{\hspace{15pt}}一行一个整数 n\left(1\leqq n\leqq 9\right)。


输出描述:
{\hspace{15pt}}按字典序输出所有排列，每行输出 n 个整数，数字之间用单个空格分隔。
示例1

输入

3

输出

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

备注:

算法知识视频讲解
添加回答
C
人生有三乐头像 人生有三乐
C语言版本的dfs

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
//这个全排列好啊，学会了可以作为其他题目全排列的基础，其他很多题目会全排列其实可以解决很多问题，就比如前面那个火车进站的问题
int n;
int *res;  //保存结果的数组
int *used;     //标记i这个数是否被使用过了
int *stack;   //临时保存结果的数组，这个应该是一个栈，存储选取元素的顺序
int stack_top=-1;  //栈顶

//判断所有数字是否都被使用过
bool ALL_USED(){
    for (int i=1; i<=n; i++) {
        if (used[i]==0) {
            return false;
        }
    }
    return true;
}

void dfs(int *array)
{
    //退出条件
    if (ALL_USED()) {
        //保存结果，从栈底到栈顶
        for (int i=0; i<=stack_top; i++) {
            res[i]=stack[i];
        }
        for (int i=0; i<=stack_top; i++) {
            //输出结果
            printf("%d ",res[i]);
        }printf("\n");
        return;
    }
    //单层逻辑    
    for (int i=1;i<=n; i++) {
        //选取
        if (used[i]==0) {  //这个数字没有被使用过
            used[i]=1;//标记被使用
            stack[++stack_top]=i;//入栈 ,应该是把第i个数入栈
            dfs(array);
            //回溯，便于另一个子问题使用
            used[i]=0;
            //清理
            stack[stack_top--]=-1;//出栈
        }
    }
   
}

int main() {
   
    scanf("%d",&n);
    res=malloc(sizeof(int)*(n+1));
    used=malloc(sizeof(int)*(n+1));//记录这个数字是否被使用过
    memset(used, 0, sizeof(used));
    stack=malloc(sizeof(int)*(n+1));
    int array[n+1];  //存好所有数，0是不需要的
    for (int i=0;  i<=n; i++) {  //初始化所有数
        array[i]=i;
    }

    dfs(array);
    return 0;
}
发表于 2025-10-16 11:57:17 回复(0)
提交观点

问题信息

dfs
难度：
3条回答 178浏览

热门推荐

相关试题

全排列

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号