class Solution {
public:vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> ans;back(nums,0,ans);return ans;}void back(vector<int>& nums,int n,vector<vector<int>>& ans){int i;if(n==nums.size()-1)ans.push_back(nums);for(i=n;i<nums.size();i++){swap(nums[i],nums[n]);back(nums,n+1,ans);swap(nums[i],nums[n]);}}
};

77.組合

77. 組合

題目

給定兩個(gè)整數(shù)?n?和?k，返回范圍?[1, n]?中所有可能的?k?個(gè)數(shù)的組合。

你可以按?任何順序?返回答案。

示例 1：

輸入：n = 4, k = 2
輸出：
[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],
]

示例 2：

輸入：n = 1, k = 1
輸出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

題解

設(shè)定一個(gè)count，計(jì)算每一個(gè)的數(shù)量，當(dāng)count==k時(shí)候，就放入數(shù)組。這是跟之前不太一樣的，之前的是進(jìn)行排列組合。這個(gè)有點(diǎn)像選擇排列。

從1-n開始，設(shè)置一個(gè)額外的數(shù)組來存儲(chǔ)每一次的結(jié)果。count動(dòng)態(tài)變化，將i賦給后count加一，dfs中從（i+1，n）選一個(gè)數(shù)字?；厮莺骳ount--。

class Solution {
public:vector<vector<int>> combine(int n, int k) {vector<vector<int>> ans;vector<int> c(k,0);int count;dfs(n,k,1,ans,c,count);return ans;}void dfs(int n,int k,int level,vector<vector<int>>& ans,vector<int>& c,int& count){int i;if(count==k){ans.push_back(c);return ;}for(i=level;i<=n;i++){c[count++]=i;dfs(n,k,i+1,ans,c,count);--count;}}
};

79.單位搜索

79. 單詞搜索

題目

給定一個(gè)?m x n?二維字符網(wǎng)格?board?和一個(gè)字符串單詞?word?。如果?word?存在于網(wǎng)格中，返回?true?；否則，返回?false?。

單詞必須按照字母順序，通過相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

示例 1：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
輸出：true

示例 2：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
輸出：true

示例 3：

輸入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
輸出：false

提示：

• m == board.length
• n = board[i].length
• 1 <= m, n <= 6
• 1 <= word.length <= 15
• board?和?word?僅由大小寫英文字母組成

題解

類似的套路。

dfs+回溯法，首先定義一個(gè)visit，來標(biāo)記每一次搜索的時(shí)候該位置是否被標(biāo)記過，防止同一個(gè)位置被多次訪問。

對(duì)于一個(gè)位置，要進(jìn)行邊界判斷，是否越界。接著判斷是否已經(jīng)訪問過，是否已經(jīng)成功找到，是否該位置的字母與目標(biāo)字母不同。

dfs，往四周搜索。

class Solution {
public:bool exist(vector<vector<char>>& board, string word) {if(board.empty())return false;int m=board.size(),n=board[0].size();vector<vector<bool>> visit(m,vector<bool>(n,false));int i,j;bool find=false;for(i=0;i<m;i++){for(j=0;j<n;j++)back(i,j,board,word,find,visit,0);}return find;}void back(int i,int j,vector<vector<char>>& board,string& word,bool& find,vector<vector<bool>>& visit,int level){if(i<0||i>=board.size()||j<0||j>=board[0].size())return ;if(visit[i][j]||find||board[i][j]!=word[level])return ;if(level==word.size()-1){find=true;return ;}visit[i][j]=true;back(i+1,j,board,word,find,visit,level+1);back(i-1,j,board,word,find,visit,level+1);back(i,j+1,board,word,find,visit,level+1);back(i,j-1,board,word,find,visit,level+1);visit[i][j]=false;}
};

51.N皇后

51. N 皇后

題目

按照國際象棋的規(guī)則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。

n?皇后問題?研究的是如何將?n?個(gè)皇后放置在?n×n?的棋盤上，并且使皇后彼此之間不能相互攻擊。

給你一個(gè)整數(shù)?n?，返回所有不同的?n?皇后問題?的解決方案。

每一種解法包含一個(gè)不同的?n 皇后問題?的棋子放置方案，該方案中?'Q'?和?'.'?分別代表了皇后和空位。

示例 1：

輸入：n = 4
輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解釋：如上圖所示，4 皇后問題存在兩個(gè)不同的解法。

示例 2：

輸入：n = 1
輸出：[["Q"]]

提示：

• 1 <= n <= 9

題意

N皇后，需要三個(gè)標(biāo)記函數(shù)，一個(gè)是列，一個(gè)是主對(duì)角線，另外一個(gè)是副對(duì)角線。

因?yàn)槊恳恍锌隙〞?huì)放一個(gè)皇后，一行一行遍歷，當(dāng)成功遍歷到最后一行并且成功放好皇后即可。所以不需要設(shè)行的標(biāo)記函數(shù)。

這個(gè)時(shí)候我們可以從第一行開始，按列遍歷。判斷該列是否為false，該主對(duì)角線是否為false，副對(duì)角線是否為false。如果是則下一列，如果不是就將該位置置為Q，然后對(duì)下一行進(jìn)行同樣的尋找?；厮莘?#xff0c;找完后記得將位置和標(biāo)記函數(shù)還原。

這個(gè)對(duì)角線和副對(duì)角線。可以畫在坐標(biāo)上，一個(gè)為y=x+b，一個(gè)為y=-x+b。

所以b=y-x，為了使b>0，因此我們加上n。另外一個(gè)為y+x。

class Solution {
public:vector<vector<string>> solveNQueens(int n) {vector<vector<string>> ans;if(n==0)return {};vector<string> board(n,string(n,'.'));vector<bool> c(n,false),l(2*n-1,false),r(2*n-1,false);back(n,ans,board,c,l,r,0);return ans;}void back(int n,vector<vector<string>>& ans,vector<string>& board,vector<bool>& c,vector<bool>& l,vector<bool>& r,int row){if(row==n){ans.push_back(board);return ;}int i;for(i=0;i<n;i++){if(c[i]||l[row-i+n]||r[row+i]){continue;}board[row][i]='Q';c[i]=l[row-i+n]=r[row+i]=true;back(n,ans,board,c,l,r,row+1);board[row][i]='.';c[i]=l[row-i+n]=r[row+i]=false;}}
};

總結(jié)

對(duì)于回溯法，首先找到邊界條件以及結(jié)束的條件。一般為設(shè)置的i等于行數(shù)。

邊界條件一般為不要越界。

一般還需要設(shè)置標(biāo)記函數(shù)。然后一行一行進(jìn)行訪問或者一個(gè)位置一個(gè)位置的訪問，訪問過的標(biāo)記函數(shù)置為true。接著繼續(xù)下一個(gè)或者下一行（一般是遞歸）。然后結(jié)束后還原上面的標(biāo)記函數(shù)以及board（一般會(huì)設(shè)置一個(gè)作為答案）。符合的就push_back到ans數(shù)組中去。