46 lines
1.3 KiB
C++
46 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
const int N = 110;
|
||
//深搜全排列
|
||
int path[N];
|
||
//是否使用过
|
||
bool st[N];
|
||
//数字个数
|
||
int n;
|
||
|
||
/**
|
||
* 功能：模拟整个全排列的过程，step是指当前是第几个箱子
|
||
* @param step
|
||
*/
|
||
void dfs(int step) {
|
||
if (step == n) { //如果走到了第n个箱子面前，就结束
|
||
for (int i = 1; i <= n; i++) printf("%d ", path[i]);//输出当前存储的路径
|
||
printf("\n");
|
||
return;
|
||
}
|
||
//每个数字都有机会放到这个箱子里去
|
||
for (int i = 1; i <= n; i++) {
|
||
//如果没用过,查找没有使用过的数字！
|
||
if (!st[i]) {
|
||
//准备使用，标识用过了
|
||
st[i] = true;
|
||
/*注意：这里回溯的是什么？是状态，是标识，是有没有使用过，这和题目相关，有的题目要求用过不能再用，有的可以！*/
|
||
|
||
path[step + 1] = i; //放入路径
|
||
dfs(step + 1); //在此前提下继续下一个箱子的操作,一条完整路线！！！！画二叉树描述状态
|
||
|
||
/*回溯，让它可以继续使用*/
|
||
st[i] = false;
|
||
}
|
||
}
|
||
}
|
||
|
||
int main() {
|
||
//一共3个数字
|
||
n = 3;
|
||
//站在零号箱子面前，开始！
|
||
dfs(0);
|
||
return 0;
|
||
}
|