题目描述:
算法设计步骤:
从 1 循环遍历到 n, 每个值都可以是某个排列的开始。从起始值进行递归,递归到 数量与 n 相等即可终止递归。用 vis[] 数组判断某个值是否在当前序列已经出现过,没有出现过就放到 vector 中,然后继续向下递归。每次递归结束后都要进行处理现场, 将标记数组改成未标记(某个数在这个序列被使用后,在下一个序列要想使用,就需要清除标记)。Code:
#include <vector> #include <cstdio> #include <string> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int n; vector<int>ve; int vis[10]; void DFS(int x,int deep) { // 够 n 个数之后就可以输出啦 if(deep == n) { for(int i = 0; i < ve.size(); i ++) { cout << ve[i] << " "; } cout << endl; return ; } for(int i = 1; i <= n; i ++) { /* 如果不用 vis[] 数组进行标记,此时我们只能判断序列中上一个数存在于序列中 上上一个数无法进行判断,可能就会出现重复,所以选用 标记数组进行标记 */ if(x == i || vis[i]) continue; ve.push_back(i); vis[i] = 1; // 向下一个地方进行递归 DFS(i,deep + 1); ve.pop_back(); vis[i] = 0; } return ; } int main(void) { cin >> n; for(int i = 1; i <= n; i ++) { // 取这个数,放到当前排列中 ve.push_back(i); // 进行标记,避免重复 vis[i] = 1; // 递归 DFS(i,1); // 用完这个数之后要从当前顺序中去掉,因为数就那么多,别的序列还要用 ve.pop_back(); // 同时去除标记 vis[i] = 0; } return 0; }不用 vis[] 数组 出现的结果:
