理解题目

输入一个n，输出n个数字的排列（1-n）的所有情况

解题思路

使用深度优先搜索，定义两个数组，state[N]数组用来存储排列中的数字，used[N]数组用来判断（1-n）中元素是否被使用过，从第一个位置搜索，从（1-n）判断元素是否被使用过，没有被使用过，加入state数组，进行下一层dfs，执行完之后，进行恢复现场。如果u（state中元素数量）达到n，则遍历state数组中的元素，打印出当前排列情况。

• c++代码

#include<iostream>
using namespace std;
const int N=10;
int n;
int state[N];
int used[N];
void dfs(int u){
    //边界
    if(u>n){
        for(int i=1;i<=n;i++){
            printf("%d ",state[i]);
        }
        puts("");
        return;
    }

    //枚举每个分支,当前位置可以填那些数字
    for(int i=1;i<=n;i++){
        if(!used[i]){
            state[u]=i;
            used[i]=1;
            dfs(u+1);

            //恢复现场
            used[i]=0;
        }
    }
}
int main(){
    scanf("%d",&n);
    dfs(1);
    return 0;
}

• java代码

import java.util.Scanner;
public class Main{
    static int N = 10;
    static int n;// 表示元素的个数
    static int[] state = new int[N]; // 用来存储当前情况的数字
    static int[] used = new int[N]; //用来判断数字有没有被选中 
    static void dfs(int u){
        if(u > n){
            for(int i = 1; i <= n; i++){
                System.out.print(state[i] + " ");
            }
            System.out.println();
        }
        //枚举每一个分支
        for(int i = 1; i <= n;i ++){ //遍历所有的数字，找到没有放入坑位的数字
            if(used[i] == 0){
                state[u] = i; // 没有使用过，将当前元素放入数组中
                used[i] = 1;
                dfs(u + 1);
                //恢复现场
                used[i] = 0;
            }

        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        dfs(1);
    }

}

• python

N = 10
n = int(input()) 
state = [0] * N # 定义数组并初始化
used = [False] * N 
def dfs(u):
    if(u > n):
        for i in range(1, n + 1):
            print(state[i], end = ' ')
        print('') # python的输出没有指定结尾的话 默认带回车

    for i in range(1, n + 1):
        if(used[i] == False):
            state[u] = i
            used[i] = True
            dfs(u + 1)
            used[i] = False 

dfs(1)