东方博宜OJ 1654：全部排列问题 ← 递归 + 各位可重复

【题目来源】https://oj.czos.cn/p/1654【题目描述】输入 n 输出 1...n 个数的全部排列。全部排列中数字可以重复。例如输入 3输出全部排列的结果如下111、112、113、121、122、123、131、132、133、211、212、213、221、222、223、231、232、233、311、312、313、321、322、323、331、332、333。【输入格式】一个整数 n1n≤6。【输出格式】按照由小到大的顺序输出 1…n 这 n 个数的全部排列情况。【输入样例】2【输出样例】11122122【数据范围】1n≤6【算法分析】●各位不可重复的全排列问题https://blog.csdn.net/hnjzsyjyj/article/details/148295326的代码如下所示。#include bits/stdc.h using namespace std; const int N10; int a[N],st[N]; int n; void dfs(int pos) { if(posn1) { for(int i1; in; i) { couta[i]; } coutendl; return; } for(int i1; in; i) { if(st[i]0) { a[pos]i; st[i]1; dfs(pos1); st[i]0; } } } int main() { cinn; dfs(1); return 0; } /* in: 2 out: 11 12 21 22 */● 关于对上述代码中 st[i]0; 的理解在深度优先搜索DFS的回溯框架中st[i]0; 是实现多分支探索的核心机制。逻辑流程如下1. 分支展开在位置 pos选择数字 ist[i] 1进入一个分支继续搜索。2. 分支回溯当该分支及其所有子分支都探索完毕后必须撤销当前选择st[i] 0使数字 i 重新可用。3. 状态重置只有这样同一层级位置 pos的下一个循环迭代才能以相同的初始状态尝试其他数字从而实现从 pos 到 pos1 的多分支并行探索效果。【算法代码】● 本题是各位可重复的全排列问题代码更短。如下所示。#include bits/stdc.h using namespace std; const int N10; int a[N]; int n; void dfs(int pos) { if(posn1) { for(int i1; in; i) { couta[i]; } coutendl; return; } for(int i1; in; i) { a[pos]i; dfs(pos1); } } int main() { cinn; dfs(1); return 0; } /* in: 2 out: 11 12 21 22 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/148295326