先上題

再上代碼

這個(gè)問題的棘手之處就在于n是不確定的。

如果n確定，為了按照字典序輸出，我們可以通過循環(huán)的嵌套以及幾個(gè)條件判斷直接輸出，比如這樣：

但n是不確定的，我們并不知道要套幾層循環(huán)，這就需要遞歸的使用。

遞歸的核心有三點(diǎn)：起始點(diǎn)、遞推關(guān)系和邊界條件。

在這個(gè)問題里，起始點(diǎn)可以從第一位開始。

而遞推關(guān)系體現(xiàn)為：我們?nèi)绻辛诉@個(gè)數(shù)選取個(gè)數(shù)后在前位上所有的排列，我們可以在它的基礎(chǔ)上給出這個(gè)數(shù)在前位上所有選取后的排列。

對(duì)于每一種已知的排列，我們只需要從到遍歷一遍，分別找到所有在這一個(gè)排列中沒有出現(xiàn)過的數(shù)字，放在第位上，便可以得到需要的結(jié)果。

而邊界條件就是，也即當(dāng)我們把前位都填充完之后，我們已經(jīng)得到了一種排列，只需要輸出即可。

到這里這個(gè)遞歸的思路已經(jīng)了然了，剩下的是一個(gè)小的優(yōu)化，也就是數(shù)組的加入。

在我們從到遍歷的時(shí)候，需要與前面的數(shù)比對(duì)以確定是否重復(fù)，這是一筆不小的開銷。為了減少這個(gè)開銷，我們選擇開一個(gè)sgn數(shù)組，用于標(biāo)志該數(shù)是否已在前位中被選取。

當(dāng)我們?cè)诘?img type="latex" class="latex" src="https://api.bilibili.com/x/web-frontend/mathjax/tex?formula=x" alt="x">位上放置一個(gè)數(shù)時(shí)，我們將置為，表示該數(shù)已被選取，而當(dāng)后面的函數(shù)，即調(diào)用結(jié)束時(shí)，我們將置為，因?yàn)闊o論之后是還在該層繼續(xù)循環(huán)，還是跳出循環(huán)，該位都不再選取。

把兩個(gè)代碼作比較可能會(huì)好理解一些：

中的循環(huán)就對(duì)應(yīng)中的循環(huán)，只不過中循環(huán)的嵌套是直接寫出來的，中的循環(huán)嵌套則通過遞歸實(shí)現(xiàn)。中取不同變量名是為了區(qū)分，而中不同層的循環(huán)在不同的函數(shù)中，不需要在名字上做區(qū)分。

中的條件判斷就對(duì)應(yīng)中對(duì)的判斷以及反復(fù)的置置。

中最后一次循環(huán)正常結(jié)束便可輸出一個(gè)結(jié)果，而中則是到第時(shí)，遞歸到最底層，輸出結(jié)果。不同點(diǎn)則在于的循環(huán)中完整保留了各位的信息，而需要一個(gè)數(shù)組來存放這些信息。

以上。

遞歸還是要多寫，剛接觸的時(shí)候確實(shí)會(huì)比較懵，但把三個(gè)核心點(diǎn)寫好，遞歸還是可以以簡(jiǎn)單的思路實(shí)現(xiàn)的。