题目描述
给定一个整数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
思路
dfs + 回溯法
dfs 特性 dfs通过是深度遍历,如果树的高度为h,它会不断从根向下遍历,直到遇到空节点,返回到上一个记录的节点。其特性满足栈的后进去后出。所以其空间存储方式为stack, 大小为h。
回溯法 算法中对应已经遍历过的节点,为了防止重复的使用,需要标记下该节点被访问过。当返回到上一层,为了不影响上一层其他数的使用,需要将之前遍历过的节点恢复现场。
java
import java.util.Scanner;
public class Main{
static int n; // n层
static int N = 10;
static int[] path = new int[N]; // 路径
static boolean[] st = new boolean[N]; // 是否被访问
private static void dfs(int u) {
if (u == n) {
for (int i = 0; i < n; i++) {
System.out.print(path[i] + " ");
}
System.out.println();
return;
}
for (int i = 1; i <= n; i++) { // 1 - n 数
if (!st[i]) { // 未被访问
path[u] = i; // 记录第u层数的值
st[i] = true; // 当前节点访问过
dfs(u + 1); // 下一层
st[i] = false; // 回溯
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
dfs(0);
}
}
python
N = 10
path = [0] * N
st = [0] * N
def dfs(u):
global n
if u == n:
for i in range(0, n):
print(path[i], end=" ")
print()
return
for i in range(1, n + 1):
if st[i] == 0:
path[u] = i
st[i] = 1
dfs(u + 1)
st[i] = 0
def main():
global n
n = int(input())
dfs(0)
if __name__ == '__main__':
main()
c++
#include <iostream>
using namespace std;
const int N = 10;
int n;
int path[N]; //路径
bool st[N]; //节点是否被访问过
void dfs(int u){
if(u == n){ //最后一层访问过后,打印结果
for(int i = 0; i < n; i++) printf("%d ", path[i]);
puts("");
return;
}
for(int i = 1; i <= n; i ++){
if(!st[i]){
path[u] = i; //记录第u层的路径节点
st[i] = true; //记录访问过的节点
dfs(u + 1); //访问下一层u + 1
st[i] = false; //被访问过的节点恢复现场
}
}
}
int main(){
cin >> n;
dfs(0);
return 0;
}