侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 29 条评论

目 录CONTENT

文章目录

【DFS】排列数字

GabrielxD
2022-11-11 / 0 评论 / 0 点赞 / 299 阅读 / 485 字
温馨提示:
本文最后更新于 2022-11-11,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

842. 排列数字


给定一个整数 nn,将数字 1n1 \sim n 排成一排,将会有很多种排列方法。

现在,请你按照字典序将所有的排列方法输出。

输入格式

共一行,包含一个整数 nn

输出格式

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

数据范围

1n71 \le n \le 7

输入样例:

3

输出样例:

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

解题

方法一:DFS

思路

image-20221111154114411

找排列就相当于向长度为 nn 的数组中放入 1n1 \sim n,所以递归地为数组中的 0n10 \sim n-1 位填充数字:

  • 如果填到第 nn 位就说明已经找出了一种排序方式,输出这种排序并退出递归。
  • 否则从 1n1 \sim n 中找出当前排列中还没有的数字填进去进行下一次递归,并在递归执行完后回溯(还原 vispath)。

代码

#include <iostream>

using namespace std;

const int N = 10;
int n, path[N];
bool vis[N];

void dfs(int idx) {
    if (idx == n) {
        for (int i = 0; i < n; ++i) printf("%d ", path[i]);
        puts("");
        return;
    }
    for (int x = 1; x <= n; ++x) {
        if (!vis[x]) {
            path[idx] = x;
            vis[x] = true;
            dfs(idx + 1);
            vis[x] = false;
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(0);
    
    return 0;
}
import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static int[] path;
    static boolean[] vis;
    
    static void dfs(int idx) {
        if (idx == n) {
            for (int i = 0; i < n; ++i) System.out.print(path[i] + " ");
            System.out.print("\n");
            return;
        }
        for (int x = 1; x <= n; ++x) {
            if (!vis[x]) {
                path[idx] = x;
                vis[x] = true;
                dfs(idx + 1);
                vis[x] = false;
            }
        }
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        path = new int[n];
        vis = new boolean[n + 1];
        dfs(0);
    }
}

0

评论区