---

一、括號(hào)生成

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 1、全局變量string path;vector<string> ret;int right = 0, left = 0, n = 0;vector<string> generateParenthesis(int _n) {n = _n;dfs();return ret;}void dfs(){// 1、出口if(right == n){ret.push_back(path);return;}// 2、添加左括號(hào)if(left < n){path.push_back('(');left++;dfs();path.pop_back(); // 恢復(fù)現(xiàn)場(chǎng)left--;}if(right < left) // 3、添加右括號(hào){path.push_back(')');right++;dfs();path.pop_back(); // 恢復(fù)現(xiàn)場(chǎng)right--;}}
};

3、解析

二、組合

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 1、全局變量int n = 0; // 1-nint k = 0; // 幾個(gè)數(shù)vector<int> path; // 路徑vector<vector<int>> ret; // 增加的路徑函數(shù)vector<vector<int>> combine(int _n, int _k) {n = _n;k = _k;dfs(1); // 2、dfsreturn ret;}void dfs(int _pos){// 1、函數(shù)遞歸出口if(path.size() == k){ret.push_back(path);return;}// 2、遍歷--剪枝for(int pos = _pos; pos <= n; pos++){path.push_back(pos);dfs(pos + 1); // pos下一個(gè)數(shù)進(jìn)行遞歸實(shí)現(xiàn)剪枝path.pop_back(); // 回溯--恢復(fù)現(xiàn)場(chǎng)         }}
};

3、解析

三、目標(biāo)和

1、題目描述

leetcode鏈接

2、代碼

全局變量的超時(shí)代碼：
原因在于nums的長(zhǎng)度最長(zhǎng)有20，其2^20次方太大了。但是leetcode居然通過了。

class Solution 
{
public:// 1、全局變量int ret; // 返回int aim; // 目標(biāo)值int path; // 路徑int findTargetSumWays(vector<int>& nums, int target) {aim = target;dfs(nums, 0);return ret;}void dfs(vector<int>& nums, int pos){// 1、遞歸出口if(pos == nums.size()){if(path == aim){ret++;}return;}// 2、加法path += nums[pos];dfs(nums, pos + 1);path -= nums[pos]; // 恢復(fù)現(xiàn)場(chǎng)// 3、減法path -= nums[pos];dfs(nums, pos + 1);path += nums[pos]; // 恢復(fù)現(xiàn)場(chǎng)}
};

path作為參數(shù)的正確代碼：

class Solution 
{
public:// 1、全局變量int ret; // 返回int aim; // 目標(biāo)值int findTargetSumWays(vector<int>& nums, int target) {aim = target;dfs(nums, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int path){// 1、遞歸出口if(pos == nums.size()){if(path == aim){ret++;}return;}// 2、加法path += nums[pos];dfs(nums, pos + 1, path);path -= nums[pos]; // 恢復(fù)現(xiàn)場(chǎng)// 3、減法path -= nums[pos];dfs(nums, pos + 1, path);path += nums[pos]; // 恢復(fù)現(xiàn)場(chǎng)}
};

3、解析

四、組合總和

1、題目描述

leetcode鏈接

2、代碼

解法一：

class Solution 
{
public:// 1、全局變量vector<vector<int>> ret; // 返回vector<int> path; // 路徑int aim; // 記錄targetvector<vector<int>> combinationSum(vector<int>& candidates, int target) {aim = target;dfs(candidates, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){// 1、遞歸出口if(sum == aim){ret.push_back(path);return;}if(sum > aim){return;}// 循環(huán)for(int i = pos; i < nums.size(); i++){path.push_back(nums[i]);sum += nums[i];dfs(nums, i, sum); // 還是從開始path.pop_back(); // 恢復(fù)現(xiàn)場(chǎng)sum -= nums[i];}}
};

解法二：

class Solution 
{
public:// 1、全局變量vector<vector<int>> ret; // 返回vector<int> path; // 路徑int aim; // 記錄targetvector<vector<int>> combinationSum(vector<int>& candidates, int target) {aim = target;dfs(candidates, 0, 0);return ret;}void dfs(vector<int>& nums, int pos, int sum){// 1、遞歸出口if(sum == aim){ret.push_back(path);return;}if(sum > aim || pos == nums.size()){return;}// 循環(huán)for(int k = 0; k * nums[pos] + sum <= aim; k++){if(k){path.push_back(nums[pos]);}dfs(nums, pos + 1, sum + k * nums[pos]);}// 恢復(fù)現(xiàn)場(chǎng)for(int k = 1; k * nums[pos] + sum <= aim; k++){path.pop_back();}}
};

3、解析

解法一：

解法二：

五、字母大小寫全排列

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量string path; // 路徑vector<string> ret; // 返回vector<string> letterCasePermutation(string s) {dfs(s, 0); // 將s這個(gè)字符串的第0個(gè)位置進(jìn)行傳參return ret;}void dfs(string s, int pos){// 遞歸出口if(pos == s.length()){ret.push_back(path);return;}// 先記錄一下當(dāng)前的字母char ch = s[pos];// 不改變path.push_back(ch);dfs(s, pos + 1);path.pop_back(); // 恢復(fù)現(xiàn)場(chǎng)// 改變if(ch < '0' || ch > '9'){// 進(jìn)行改變大小寫函數(shù)ch = Change(ch);path.push_back(ch);dfs(s, pos + 1); // 往下一層遞歸path.pop_back(); // 恢復(fù)現(xiàn)場(chǎng)}}char Change(char ch){if(ch >= 'a' && ch <= 'z'){ch -= 32;}else{ch += 32;}return ch;}
};

3、解析

六、優(yōu)美的排列

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量int ret; // 返回bool check[16]; // 判斷相對(duì)應(yīng)位置是true還是falseint countArrangement(int n) {dfs(1, n); // 下標(biāo)從1開始return ret;}void dfs(int pos, int n){// 遞歸出口if(pos == n + 1) // 因?yàn)槭菑?開始的{ret++; // 只用做數(shù)的統(tǒng)計(jì)即可return;}// 循環(huán)for(int i = 1; i <= n; i++){if(check[i] == false && (pos % i == 0 || i % pos == 0)){check[i] = true; // 表示用了dfs(pos + 1, n); // 遞歸到下一層check[i] = false; // 恢復(fù)現(xiàn)場(chǎng)}}}
};

3、解析

七、N皇后

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量bool checkcol[10]; // 列bool checkG1[20]; // 主對(duì)角線bool checkG2[20]; // 副對(duì)角線vector<string> path; // 路徑vector<vector<string>> ret; // 返回int n; // 全局變量nvector<vector<string>> solveNQueens(int _n) {n = _n;// 初始化棋盤path.resize(n);for(int i = 0; i < n; i++){path[i].append(n, '.');}dfs(0);return ret;}void dfs(int row) // 行{// 遞歸出口if(row == n){ret.push_back(path);return;}for(int col = 0; col < n; col++) // 每一行所在的列位置{if(checkcol[col] == false/*一整列*/ && checkG1[row - col + n] == false/*y-x+n*/ && checkG2[row + col] == false/*y+x*/) // 判斷條件進(jìn)入{path[row][col] = 'Q';checkcol[col] = checkG1[row - col + n] = checkG2[row + col] = true;dfs(row + 1);// 恢復(fù)現(xiàn)場(chǎng)path[row][col] = '.';checkcol[col] = checkG1[row - col + n] = checkG2[row + col] = false;}}}
};

3、解析

這里我們著重在剪枝方面上面的講解，我們重點(diǎn)需要明白N皇后剪枝的作用，因?yàn)榛屎笫悄艹詸M的一整行，豎的一整列，主對(duì)角線和副對(duì)角線一整個(gè)，這里原本是要循環(huán)四次，但是我們經(jīng)過想法發(fā)現(xiàn)其實(shí)只需要判斷三個(gè)位置即可，第一個(gè)位置是豎著的，第二個(gè)位置是主對(duì)角線，第三個(gè)位置是副對(duì)角線，因?yàn)闄M著的一行是不需要進(jìn)行判斷的，因?yàn)槲覀兊乃悸肥且砸徽袨橐粋€(gè)視角，從左往右依次填的！我們根據(jù)簡(jiǎn)單的數(shù)學(xué)原理，主對(duì)角線是y=x+b的，而由于會(huì)出現(xiàn)負(fù)數(shù)情況，我們左右兩邊各加一個(gè)n即可，我們此時(shí)b就為：y-x+n。我們副對(duì)角線是y=-x+b，我們的b為y+x即可！那我們接下來的思路畫出決策樹以后只需要考慮回溯的問題，我們恢復(fù)現(xiàn)場(chǎng)只需要將用過的全部變成沒用過的即可。

八、有效的數(shù)獨(dú)

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 全局變量bool row[9][10]; // 行坐標(biāo)加值bool col[9][10]; // 列坐標(biāo)加值bool grid[3][3][10]; // 棋盤坐標(biāo)加值bool isValidSudoku(vector<vector<char>>& board) {for(int i = 0; i < 9; i++) // 行{for(int j = 0; j < 9; j++) // 列{if(board[i][j] != '.') // 數(shù)字的時(shí)候{int num = board[i][j] - '0'; // 記錄一下數(shù)if(row[i][num] == true || col[j][num] == true || grid[i / 3][j / 3][num] == true){return false;}row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;}}}return true;}
};

3、解析