? ? ? ? ? ? ? ? ? ? ? ? ? ?歡迎訪問(wèn)殺馬特主頁(yè)：小小殺馬特主頁(yè)呀！

目錄

前言：

例題一·全排列：

1.題目介紹：

2.思路匯總：

3.代碼解答：

例題二·子集：

題目敘述：

解法一：

1.思路匯總：

2.代碼解答：

解法二：

?

1.思路匯總：

2.代碼解答：

?

文末小總結(jié)：?

---

前言：

本篇采用兩道例題來(lái)講解利用枚舉元素的方法使用決策樹(shù)通過(guò)遞歸以及穿插回溯來(lái)解答類(lèi)似此類(lèi)問(wèn)題的系列模版操作(涉及全局變量以及引用傳參使用需要回溯問(wèn)題與具體什么時(shí)候使用等)。

當(dāng)我們使用全局變量大都就要手動(dòng)的回溯了，因?yàn)樗貧w到上一層自己不會(huì)改變，這里既可以選擇全局變量又可以選擇引用傳參，但是比如一個(gè)遞歸函數(shù)需要使用多個(gè)變量，這時(shí)候引用傳參就麻煩了，故需要我們使用全局變量了，因此視情況而定（本篇我們都使用的是全局變量）。

例題一·全排列：

1.題目介紹：

?歡迎大家來(lái)挑戰(zhàn)：leetcode原題鏈接：?. - 力扣（LeetCode）

2.思路匯總：

畫(huà)出決策樹(shù)，然后令dfs函數(shù)能幫我們完成此元素位置（從其上到末的path都放入ret）然后對(duì)于這個(gè)數(shù)組就是要遍歷它了，由于我們要定義的path是全局遍歷故

要考慮回溯（復(fù)原操作）：這里就是我們每次往后遞歸，不能出現(xiàn)前面的元素，故這里開(kāi)一個(gè)bool類(lèi)型數(shù)組記錄一下

（一開(kāi)始是false，變成true就是已經(jīng)出現(xiàn)了，故不進(jìn)行操作繼續(xù)循環(huán)）

終止條件：當(dāng)path滿了（等于nums的size）就返回就行了。

思路：從下標(biāo)0開(kāi)始遍歷數(shù)組，遍歷到一個(gè)就放入path，記錄狀態(tài)，然后繼續(xù)下面遞歸，依次重復(fù)，

最后肯定會(huì)path等于size然后就放入ret，然后回溯：在上一層完成刪除path的back即恢復(fù)現(xiàn)場(chǎng)的操作，每一次完成一條路線就往回溯，最后歸到第一次for循環(huán)到退出。

決策圖解：

3.代碼解答：

class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7]={false};//如果換成vector的bool類(lèi)型只能用原數(shù)組指針區(qū)間初始化void dfs(vector<int>& nums){if(path.size()==nums.size()){ret.push_back(path);//終止條件return;}for(int i=0;i<nums.size();i++){if(check[i]==false){//使用后該狀態(tài)防止重復(fù)使用path.push_back(nums[i]);check[i]=true;dfs(nums);//回溯（恢復(fù)現(xiàn)場(chǎng)）：path.pop_back();check[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}};

例題二·子集：

?本題采取兩種解法解答，一種是葉子節(jié)點(diǎn)放入ret，另一種就是每當(dāng)遞歸到一層，這一層的path就是要存入ret的結(jié)果。

題目敘述：

??歡迎大家來(lái)挑戰(zhàn)：leetcode原題鏈接：. - 力扣（LeetCode）

解法一：

1.思路匯總：

思路：枚舉元素：分為選i位置的數(shù)和不選兩條路徑，然后往下遞歸，最后決策樹(shù)相當(dāng)于葉子節(jié)點(diǎn)的數(shù)就是我們要推進(jìn)ret的，這里可以假設(shè)dfs遞歸函數(shù)可以幫我們完成從傳入

? 的pos位置一直走到葉子位置的所有分支路徑最后的到葉子節(jié)點(diǎn)的path都放入ret，然后在第一次分別傳入它的左支和右支就可以了。

? 細(xì)節(jié)：注意傳入的pos的位置以及回溯的時(shí)候path的變化

?

2.代碼解答：

class Solution {
public:vector<vector<int>> ret;vector<int> path;
void dfs(vector<int>& nums,int pos){if(pos==nums.size()){ret.push_back(path);path.pop_back();//回溯return;}//可分為左支不走，右支走：//走pos位置的元素（右支）：path.push_back(nums[pos]);dfs(nums,pos+1);//不走pos位置的元素（左支）：dfs(nums,pos+1);}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}

解法二：

1.思路匯總：

思路：我們遍歷數(shù)組放入path，并且當(dāng)遞歸到下一層遍歷的時(shí)候就是當(dāng)前位置的下一個(gè)開(kāi)始，所以循環(huán)的第一個(gè)是pos位置，結(jié)合每次下一層遞歸結(jié)束回到上一層都會(huì)把下一層的

? path里面加入的nums[i]刪除即回溯，保證了每次每當(dāng)我們進(jìn)入一次遞歸第一個(gè)就是子集。?

細(xì)節(jié)：1·為什么ret添加不在for里面：這樣的話最后一次遞歸完成后無(wú)法添加最后一次的結(jié)果。

? ? ? ??2·為什么每次遞歸函數(shù)傳參是i+1不是pos+1呢:這樣的話就會(huì)導(dǎo)致遞歸回來(lái)的時(shí)候走for里的i++的時(shí)候再次傳入pos+1，又會(huì)進(jìn)行剛才的遞歸操作了，不符合預(yù)期。

2.代碼解答：

  void dfs(vector<int>& nums,int pos){ret.push_back(path);for(int i=pos;i<nums.size();i++){path.push_back(nums[i]);dfs(nums,i+1);path.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;}

文末小總結(jié)：?

像這種類(lèi)型的dfs思路就是首先根據(jù)題意采取窮舉等方法畫(huà)出決策樹(shù)，然后根據(jù)規(guī)則轉(zhuǎn)化成遞歸代碼：終止條件，遞歸操作，回溯，剪枝的判斷，其次就是合理應(yīng)用全局變量等