一、排列問題

全排列II

題目鏈接

題解

1. 這題和全排列那題框架是一樣的，就是剪枝操作不一樣
2. 同一節點出現相同元素肯定會重復，所以把同一節點的相同元素剪掉
3. 同一個數只能出現一次，用check數組剪枝
分為兩種情況進行剪枝：
1、只關心不合法的分支：
不合法的進行跳過（剪枝）
check[i] == true || ( i != 0 &&nums[i] == nums[i-1] && check[i-1] == false)
這個點是已經使用過的，或者是這個點和前一個點是相同的并且前一個點沒有使用過，i != 0保證不越界
2、只關心合法的分支：
合法的分支才進行dfs
check[i] == false && (i == 0 || nums[i] != nums[i-1] || check[i] == true)
這個點沒有被使用過并且該點為第一個點肯定可以進行dfs，或者是該點和前一個點不相同也可以dfs，或者是該點和前一個點相同，但是前一個點上一層已經使用過了，這個點這層可以繼續使用，因為它們是用的不同位置

代碼

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;bool check[9];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vector<int> nums){if(path.size() == nums.size()){ret.push_back(path);return;}// 如何把重復的數字剪掉for(int i = 0;i < nums.size();i++){// 合法的剪枝,不合法就不進行dfs// if((check[i] == false)&&// (i == 0||nums[i] != nums[i-1]||check[i-1] == true))// {//     check[i] = true;//     path.push_back(nums[i]);//     dfs(nums);//     // 恢復現場//     check[i] = false;//     path.pop_back();// }// 考慮不合法的剪枝,跳過不合法的剪枝if((check[i] == true)||(i != 0&&nums[i] == nums[i-1]&&check[i-1] == false))continue;check[i] = true;path.push_back(nums[i]);dfs(nums);// 恢復現場check[i] = false;path.pop_back();}}
};

優美的排列

題目鏈接

題解

1. 畫出決策樹
2. 全局變量的設計：ret用來記錄優美排列的個數，check數組檢查是否可以剪枝，n設計成全局變量就不需要進行傳參了
3. 剪枝：第一種剪枝不能出現重復的數，第二種剪枝不滿足整除條件的
4. 回溯：如圖我們每個位置都要進行判斷，每個位置都會走一遍，遞歸完后進行恢復現場，把最后一位pop_back
5. 遞歸出口：當path路徑的長度等于n時為遞歸出口
6. for循環的i = 1開始是因為要遍歷所有的路徑，dfs中pos+1是因為此位置遍歷完會來到下一個位置進行遍歷，畫出決策樹就很清晰了

代碼

class Solution
{
public:int n;int ret;bool check[16];vector<int> path;int countArrangement(int _n) {n = _n;dfs(1);return ret;}void dfs(int pos){if(path.size() == n){ret++;return;}for(int i = 1;i <= n;i++){if(pos % i == 0 || i % pos == 0){if(check[i] == false){check[i] = true;path.push_back(i);dfs(pos+1);// 恢復現場path.pop_back();check[i] = false;}} }}
};

二、子集問題

字母大小寫全排列

題目鏈接

題解

1. 畫出決策樹
2. 全局變量：ret記錄最終的結果，path記錄每次的路徑
3. 剪枝：沒有剪枝
4. 回溯：到達葉子節點的時候記錄完進行回溯，pop_back最后一個位置的數來到上一層
5. 遞歸出口：pos位置為n時，是最后一個數據的下一個位置，為遞歸出口
6. 這題和選和不選基本上是一樣的，子集問題，pos這個位置變或者不變然后來到下一個位置，所以dfs(pos+1)，變的情況為小寫字母時轉為大寫字母，大寫轉為小寫，不變就直接push

代碼

class Solution 
{
public:vector<string> ret;string path;vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s,int pos){// 為什么不能寫pos == s.size()if(pos == s.size()){ret.push_back(path);return;}char ch = s[pos];// 不變path.push_back(ch);dfs(s,pos+1);path.pop_back();// 變if(ch < '0' || ch > '9'){ch = change(ch);path.push_back(ch);dfs(s,pos+1);path.pop_back();}}char change(char ch){if(ch >= 'a' && ch <= 'z') ch -= 32;else ch += 32;return ch;}
};

找出所有子集的異或總和再求和

題目鏈接

題解

1. 畫出決策樹
2. 全局變量：用sum記錄最終的結果，用path記錄一個集合的異或和
3. 剪枝：沒有剪枝
4. 回溯：每次異或當前元素就抵消掉這個元素了，然后回到上一層
5. 遞歸出口：沒有遞歸出口，每次把path加到sum中即可
6. for循環中每次從pos位置開始向后枚舉，避免重復，dfs(i+1)，i+1就是數組中下一個位置的數，相當于剪枝了

代碼

class Solution 
{
public:long long sum = 0;// 記錄全部路徑的異或和long long path = 0;// 記錄一條路徑的異或和int subsetXORSum(vector<int>& nums) {dfs(nums,0);return sum;}void dfs(vector<int> nums,int pos){sum += path;for(int i = pos;i < nums.size();i++){path ^= nums[i];dfs(nums,i+1);path ^= nums[i];// 不能使用pos代替i,如果進行回溯回來,// 進行循環,path始終異或nums[pos]}}
};

三、組合問題

電話號碼的字母組合

題目鏈接

題解

1. 畫出決策樹
2. 全局變量：ret記錄最終的結果，path記錄每次的路徑，哈希表記錄下標的映射關系
3. 剪枝：沒有剪枝
4. 回溯：到達葉子節點時，pop_back最后一個元素，恢復現場
5. 遞歸出口：path的長度和給定的數組的長度相同
6. for循環把所有的數都枚舉出來了，所以i下標從0開始，dfs(pos+1)，每個位置枚舉完跳到下一個位置繼續枚舉，這題主要是建立一個hash表記錄每次的電話號碼的數字對應的映射字符串

代碼

class Solution 
{
public:vector<string> ret;string path;string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> letterCombinations(string digits) {if(digits.size() == 0) return ret;dfs(digits,0);   return ret;}void dfs(string digits,int pos){if(pos == digits.size()){ret.push_back(path);return;}for(int i = 0;i < hash[digits[pos] - '0'].size();i++){path.push_back(hash[digits[pos] - '0'][i]);dfs(digits,pos+1);// 恢復現場path.pop_back();}}
};

括號生成

題目鏈接

題解

1. 畫出決策樹
2. 全局變量：path記錄每次的路徑，ret記錄最終的結果，left記錄左括號的數量，right記錄右括號的數量
3. 剪枝：第一種右括號的數量大于等于左括號的數量，第二中左括號的數量大于等于n的數量，開始的時候只能給左擴號，右括號剪枝，左右括號相等時，不能加入右括號，左括號大于n不符合結果，等于n時，再往下加就大于n，需要剪枝
4. 回溯：如果是左括號回溯，pop_back最后一個元素，left–，如果是右括號回溯，pop_back最后一個元素，right–
5. 遞歸出口：右括號的數量等于n時，為左右括號相等的最終結果

代碼

class Solution 
{
public:vector<string> ret;string path;int left,right;vector<string> generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){if(right == n){ret.push_back(path);return ;}if(left < n){path.push_back('(');left++;dfs(n);path.pop_back();left--;}if(left > right){path.push_back(')');right++;dfs(n);path.pop_back();right--;}}
};

組合

題目鏈接

題解

1. 畫出決策樹
2. 全局變量：path記錄每次的路徑，ret記錄最終的結果，k變為全局變量，不需要多傳一個參數
3. 剪枝：不能重復出現相同的數剪枝，長度不夠k也剪枝，這題可以從pos位置開始向后枚舉，dfs(i+1)，i+1表示每次枚舉當前數的下一個位置的數，相當于進行了剪枝
4. 回溯：到達葉子節點后，每次pop_back最后一個數
5. 遞歸出口：path的長度等于k的大小

代碼

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;int k;vector<vector<int>> combine(int n, int _k) {k = _k;dfs(n,1);return ret;}void dfs(int n,int pos){if(path.size() == k){ret.push_back(path);return ;}for(int i = pos;i <= n;i++){path.push_back(i);dfs(n,i+1);path.pop_back();// 恢復現場}}
};

目標和

題目鏈接

題解

1. 畫出決策樹
2. 全局變量：ret記錄最終的結果，target變為全局變量就少傳一個參數
3. 剪枝：沒有剪枝
4. 回溯：函數自動回溯，將path作為參數，記錄每條路徑的大小，回到上一層，path變為了沒有加減之前的path
5. 遞歸出口：最終的path等于target的大小，ret++
6. 這題就是每個數兩種情況，要么加，要么減

代碼

class Solution 
{
public:int ret,target;int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums,0,0);return ret;}void dfs(vector<int>& nums,int pos,int path){if(pos == nums.size()){if(target == path)ret++;return;}// 加法,放在參數中函數幫我們自動恢復現場了dfs(nums,pos+1,path + nums[pos]);// 減法dfs(nums,pos+1, path - nums[pos]);}
};

組合總和

題目鏈接

題解

解法一：每個pos位置填
1. 畫出決策樹
2. 全局變量：ret記錄最終的結果，path記錄每條路徑，target變為全局變量就不需要傳參target了
3. 剪枝：如果這條路徑的和大于target剪枝，如果選擇的路徑重復了剪枝，這種可以使用i = pos位置開始向后枚舉，dfs(i)，i表示每次從當前這個數向后枚舉，不需要重復枚舉這個數前面的數，就避免了重復的路徑，達到了剪枝的效果
4. 回溯：sum在函數的參數中自動進行了回溯，pop_back最后一個元素，回到上一層
5. 遞歸出口：目標值等于記錄的路徑總和就找到一條路徑，加入ret中，并返回給上一層

代碼

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int> candidates,int pos,int sum){if(sum == target){ret.push_back(path);return;}// 枚舉完了所有的位置也不是target,這個總和比較小if(pos == candidates.size()) return;for(int i = pos;i < candidates.size();i++){if(sum > target) continue;path.push_back(candidates[i]);dfs(candidates,i,sum + candidates[i]);path.pop_back();}}
};

解法二：枚舉每個數的數量
1. 和解法一不一樣的地方就是dfs函數的實現不一樣

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int> candidates,int pos,int sum){if(sum == target){ret.push_back(path);return;}// 枚舉完了所有的位置也不是target,這個總和比較小if(pos == candidates.size() || sum > target) return;// 枚舉個數for(int k = 0;sum + k * candidates[pos] <= target;k++){if(k) path.push_back(candidates[pos]);dfs(candidates,pos+1,sum + k*candidates[pos]);}// 整塊恢復現場for(int k = 1;sum + k * candidates[pos] <= target;k++){path.pop_back();}}
};

總結

1. 最重要的就是畫出決策樹
2. 全局變量：一般是path記錄路徑，ret記錄各個路徑的結果
3. 剪枝：看題目分析和看決策樹
4. 回溯：一般是pop_back最后一個元素
5. 遞歸出口：看題目條件，或者是葉子節點