【DFS】排列数字

题目

842. 排列数字

---

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

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

输入格式

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

输出格式

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

数据范围

$1 \le n \le 7$

输入样例：

3

输出样例：

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

解题

方法一：DFS

思路

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

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

代码

#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);
    }
}