? ? ? ? ? ? ? ? ? ? ? ? ? ?歡迎訪問殺馬特主頁：小小殺馬特主頁呀！

目錄

前言：

例題一·全排列：

1.題目介紹：

2.思路匯總：

3.代碼解答：

例題二·子集：

題目敘述：

解法一：

1.思路匯總：

2.代碼解答：

解法二：

?

1.思路匯總：

2.代碼解答：

?

文末小總結(jié)：?

---

前言：

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

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

例題一·全排列：

1.題目介紹：

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

2.思路匯總：

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

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

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

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

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

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

決策圖解：

3.代碼解答：

class Solution {
public:vector<vector<int>> ret;vector<int> path;bool check[7]={false};//如果換成vector的bool類型只能用原數(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)場）：path.pop_back();check[i]=false;}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}};

例題二·子集：

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

題目敘述：

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

解法一：

1.思路匯總：

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

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

? 細節(jié)：注意傳入的pos的位置以及回溯的時候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)遞歸到下一層遍歷的時候就是當(dāng)前位置的下一個開始，所以循環(huán)的第一個是pos位置，結(jié)合每次下一層遞歸結(jié)束回到上一層都會把下一層的

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

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

? ? ? ??2·為什么每次遞歸函數(shù)傳參是i+1不是pos+1呢:這樣的話就會導(dǎo)致遞歸回來的時候走for里的i++的時候再次傳入pos+1，又會進行剛才的遞歸操作了，不符合預(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é)：?

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