我要招人

去企业版

首页 > 试题广场 >

全排列

[编程题]全排列

热度指数：2004 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

${\hspace{15pt}}$ 给定一个整数 $n$ ，请按 字典序 输出数字 $1\sim n$ 的所有排列。

输入描述:

一行一个整数 。

输出描述:

按字典序输出所有排列，每行输出  个整数，数字之间用单个空格分隔。

示例1

输入

输出

备注:

算法知识视频讲解

1900201910072158499

import java.util.Scanner;

import java.util.ArrayList;

// 注意类名必须为 Main, 不要有任何 package xxx 信息

public class Main {

// 递归生成全排列的方法

// listA: 当前已排列的部分

// listB: 待排列的元素集合

public static void fullPermutation(ArrayList<Integer> listA,

ArrayList<Integer> listB) {

int len_b = listB.size(); // 获取待排列元素的个数

// 基准情况：如果listB为空，说明所有元素都已排列完成

if (len_b == 0) {

for (Integer i : listA) {

System.out.print(i + " "); // 输出当前排列结果

}

System.out.println();

} else {

// 递归情况：遍历listB中的每个元素

for (int i = 0; i < len_b; i++) {

// 创建当前排列和待排列列表的副本（避免修改原列表）

ArrayList<Integer> tempA = (ArrayList<Integer>) listA.clone();

ArrayList<Integer> tempB = (ArrayList<Integer>) listB.clone();

// 从待排列列表中移除第i个元素，并添加到当前排列中

tempA.add(tempB.remove(i));

// 递归调用，继续排列剩余元素

fullPermutation(tempA, tempB);

}

public static void main(String[] args) {

Scanner input = new Scanner(System.in); // 创建Scanner对象读取输入

int n = input.nextInt(); // 读取用户输入的整数n

ArrayList<Integer> listA = new

ArrayList<>(); // 初始化当前排列列表（空）

ArrayList<Integer> listB = new ArrayList<>(); // 初始化待排列元素列表

// 初始化待排列的listB，添加1到n的整数

for (int i = 1; i <= n; i++) {

listB.add(i);

}

// 调用全排列方法

fullPermutation(listA, listB);

input.close(); // 关闭Scanner（建议添加）

}

发表于 2025-08-22 19:55:34 回复(0)

whayisn

#include <iostream>
#include <vector>
using namespace std;
void back_track(vector<int>& arr,vector<vector<int>>& result,vector<bool>& statu,vector<int>& path)
{  
    if(path.size()==arr.size())
    {
        result.emplace_back(path);
    }
    for(int i=0;i<arr.size();++i)
    {
        if(statu[i]==false)
        {
            statu[i]=true;
            path.push_back(arr[i]);
            back_track(arr,result,statu,path);
            path.pop_back();
            statu[i]=false;
        }
    }
}

int main() {
    int n;
    cin>>n;
    vector<bool> statu(n,false);
    vector<int> path;
    vector<int> arr(n,0);
    vector<vector<int>> result;
    for(int i=0;i<n;++i)
    {
        arr[i]=i+1;
    }
    back_track(arr,result,statu,path);
    for(int i=0;i<result.size();++i)
    {
        for(int j=0;j<result[0].size();++j)
        {
            cout<<result[i][j]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}

经典回溯

发表于 2025-12-13 18:06:09 回复(0)

像生201809272021899

#include <ctime>
#include <iostream>
#include <deque>
#include <vector>
using namespace std;

class test
{
public:

    static void foo(deque<int>& out_temp, vector<bool>& state,size_t const& num)
    {
        if(state.back() == false && out_temp.size() == num)
        {
            for (auto const& v : out_temp) {
                cout<< v<<" ";
            }
            cout <<endl;
            return;
        }

        for (int i = 0; i<num; ++i) 
        {
            if (state.at(i)) 
            {
                state.at(i) = false;
                out_temp.emplace_back(i+1);
                foo( out_temp, state, num);
                out_temp.pop_back();
                state.at(i) = true;
            }
        }
    }
};



int main() {
    int n;

    while (cin >> n) { // 注意 while 处理多个 case

        deque<int> out_temp;
        vector<bool> state(n,true);
        test::foo( out_temp, state, n);
    }
}
// 64 位输出请用 printf("%lld")

发表于 2025-11-14 23:04:52 回复(0)

nothing5

#include <iostream>
#include <vector>
using namespace std;

void dfs(int n, vector<int>& path, vector<bool>& visited) {
    // 如果路径长度等于n，说明找到一个排列
    if (path.size() == n) {
        for (int i = 0; i < n; i++) {
            cout << path[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    
    // 尝试每个数字
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) {          // 如果数字i还没被使用
            visited[i] = true;      // 标记为已访问
            path.push_back(i);      // 加入当前路径
            dfs(n, path, visited);  // 递归深入
            path.pop_back();        // 回溯，移除最后一个元素
            visited[i] = false;     // 取消标记
        }
    }
}

int main() {
    int n;
    cin >> n;
    
    vector<int> path;              // 存储当前路径
    vector<bool> visited(n + 1, false);  // 标记数字是否使用过
    
    dfs(n, path, visited);
    
    return 0;
}

发表于 2025-10-27 17:18:56 回复(0)

Python3

牛客341639822号

def full_permutations(arr):

def backtracking(path, used):

if len(path) == len(arr):

result.append(path[:])

return

for i in range(len(arr)):

if used[i]:

continue

path.append(arr[i])

used[i] = True

backtracking(path, used)

path.pop()

used[i] = False

result = []

backtracking([], [False] * len(arr))

return result

n = int(input())

st = [str(x) for x in range(1, n+1)]

answer = full_permutations(st)

for lis in answer:

print(' '.join(lis))

发表于 2025-10-18 11:52:16 回复(0)

人生有三乐

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)

高兴0615

import sys

n = int(input())

nums = [x for x in range(1, n+1)]

res = []

used = [False] * n

def backtrack(path):

if len(path) == n:

res.append(path[:])

return

for i in range(n):

if not used[i]:

path.append(nums[i])

used[i] = True

backtrack(path)

path.pop()

used[i] = False

backtrack([])

for i in range(len(res)):

a = res[i]

print(' '.join(str(x) for x in a))

发表于 2025-10-03 13:02:49 回复(0)

提交观点

问题信息

dfs

难度：

7条回答 49收藏 177浏览

全排列

输入描述:

输出描述:

输入

输出

备注:

问题信息

热门推荐

相关试题