HJ150 全排列

知识点dfs校招时部分企业笔试将禁止编程题跳出页面为提前适应练习时请使用在线自测而非本地IDE。描述给定一个整数 nn请按字典序输出数字 1∼n1∼n 的所有排列。输入描述一行一个整数 n(1≦n≦9)n(1≦n≦9)。输出描述按字典序输出所有排列每行输出 nn 个整数数字之间用单个空格分隔。示例1输入3复制输出1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1#include iostream #include bits/stdc.h using namespace std; int n; vectorint curr_list; vectorint visited; // 有这两个全局变量不管递归到多少层都能控制到底能塞入什么新数字进排列 void dfs(){ if(curr_list.size() n){ for(int i 0; i n; i){ cout curr_list[i] ; // 排列形成打印出来 } cout \n; return ; // 直接退出该层递归 } for(int i 1; i n; i){ // 排列从1开始 if(visited[i] 0){ // 该数字还未被塞入排列 visited[i] 1; curr_list.push_back(i); // 压入i进当前排列 dfs(); curr_list.pop_back(); visited[i] 0; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin n; visited.resize(n1, 0); dfs(); // 排列从x1开始 }