DFS

823.排列

給定一個(gè)整數(shù)n，將數(shù)字1~n排成一排，將會(huì)有很多種排列方法。

現(xiàn)在，請(qǐng)你按照字典序?qū)⑺械呐帕蟹椒ㄝ敵觥?/p>

輸入格式

共一行，包含一個(gè)整數(shù)n。

輸出格式

按字典序輸出所有排列方案，每個(gè)方案占一行。

數(shù)據(jù)范圍

1≤n≤91≤n≤9

輸入樣例：

3

輸出樣例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

思維過(guò)程：

?1.畫出遞歸數(shù)

2.思考遞邊界與如何遞歸出該樹(shù)：

? 1）每層的父節(jié)點(diǎn)有n個(gè)分支

?2）樹(shù)高為n

?3）放置數(shù)值時(shí)候，子節(jié)點(diǎn)是無(wú)法再次放置同樣的數(shù)值的，所以需要設(shè)置一個(gè)標(biāo)識(shí) bool state[n]。如1_ _，放置了1之后，就在state數(shù)組里i=1的值設(shè)為true，代表已經(jīng)用過(guò)。值得思考的是，在遞歸樹(shù)中，子節(jié)點(diǎn)返回父節(jié)點(diǎn)的時(shí)候，得將設(shè)置的true恢復(fù)為false. 如 1_ _，返回后，就得將state[1]置為false,因?yàn)樵?_ _這個(gè)遞歸中，1是可以被使用的。 以下是代碼：

#include <iostream>
#include <memory.h>
using namespace std;

//代表數(shù)組的長(zhǎng)度，同時(shí)也是遞歸樹(shù)的高度
int n;
//保存值的數(shù)組
int s[10];
//保存了哪些數(shù)據(jù)已經(jīng)用過(guò)了，下標(biāo)代表數(shù)據(jù)，值代表是否用過(guò)
bool state[10];
void dfs(int n1) {
    //邊界,說(shuō)明已經(jīng)排列完了一次
    if (n1 == n) {
        for (int i = 0; i < n; i++) cout << s[i]+1<<" ";
        cout << endl;
        return;
    }

    for (int i = 0; i < n; i++) {
         //說(shuō)明未被使用過(guò)
        if (state[i] == false) {
            //進(jìn)行s填充，并將相應(yīng)標(biāo)志位置為true
            s[n1] = i; 
            state[i] = true;
            //進(jìn)行下一次dfs
            dfs(n1 + 1);
            //回到上一層后，將原來(lái)修改為true的state恢復(fù)現(xiàn)場(chǎng)為false
            state[i] = false;
        }       
    }
}

int main() {
    cin >> n;
    dfs(0);
}