从零开始学算法-Day5

//2020.4.25 第五天了、加油

题目：递归实现排列型枚举

链接：https://ac.nowcoder.com/acm/contest/998/C
来源：牛客网

题目描述：把1∼n 这 n(n<10)个整数排成一行后随机打乱顺序，输出所有可能的次序。

求解之路：

遇到了全排列，第一想法就是先确定第一位，然后确定第二位，依次继续。其中一个确认完了就输出，然后返回上一层。所以需要一个数组去存每次的顺序，用完了就需要重置。一个vis 数组去记录已经访问过的序列。

#include <iostream>

using namespace std;
int N;
int num[13],vis[13];

void DFS(int n){

    for(int i = 1;i <= N;i++){
    if(!vis[i]){
        vis[i] = 1;
        num[n] = i;
        DFS(n+1);
        vis[i] = 0;
    }    
    }
    if(n == N){
          for(int i = 1;i <= N;i++)
            cout << num[i] << " ";
          cout << endl;
          return ;
    }
}
int main (){
    cin >> N;
    DFS(1);
    return 0;
}

总结：水题水过去的一天！！！！