DFS
823.排列
給定一個整數n，將數字1~n排成一排，將會有很多種排列方法，
現在，請你按照字典序將所有的排列方法輸出，
輸入格式
共一行，包含一個整數n，
輸出格式
按字典序輸出所有排列方案，每個方案占一行，
資料范圍
1≤n≤91≤n≤9
輸入樣例：
3
輸出樣例：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
思維程序：
? 1.畫出遞回數
?
2.思考遞邊界與如何遞回出該樹：
? 1）每層的父節點有n個分支
? 2）樹高為n
? 3）放置數值時候，子節點是無法再次放置同樣的數值的，所以需要設定一個標識 bool state[n]，如1_ _，放置了1之后，就在state陣列里i=1的值設為true，代表已經用過，值得思考的是，在遞回樹中，子節點回傳父節點的時候，得將設定的true恢復為false. 如 1_ _，回傳后，就得將state[1]置為false,因為在2_ _這個遞回中，1是可以被使用的， 以下是代碼：
#include <iostream>
#include <memory.h>
using namespace std;
//代表陣列的長度，同時也是遞回樹的高度
int n;
//保存值的陣列
int s[10];
//保存了哪些資料已經用過了，下標代表資料，值代表是否用過
bool state[10];
void dfs(int n1) {
//邊界,說明已經排列完了一次
if (n1 == n) {
for (int i = 0; i < n; i++) cout << s[i]+1<<" ";
cout << endl;
return;
}
for (int i = 0; i < n; i++) {
//說明未被使用過
if (state[i] == false) {
//進行s填充，并將相應標志位置為true
s[n1] = i;
state[i] = true;
//進行下一次dfs
dfs(n1 + 1);
//回到上一層后，將原來修改為true的state恢復現場為false
state[i] = false;
}
}
}
int main() {
cin >> n;
dfs(0);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/231275.html
標籤：C++
上一篇：動態分配的問題