何为回溯法?
在搜索到某一节点的时候,如果我们发现目前的节点(及其子节点)并不是需求目标时,我们回退到原来的节点继续搜索,并且把在目前节点修改的状态还原。记住两个小诀窍,一是按引用传状态(&),二是所有的状态修改在递归完成后回改。回溯法修改一般有两种情况,一种是修改最后一位输出,比如排列组合;一种是修改访问标记,比如矩阵里搜字符串。
46.全排列
题目给定一个不含重复数字的数组
nums
,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。示例 1:
输入:nums = [1,2,3] 输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2:
输入:nums = [0,1] 输出:[[0,1],[1,0]]示例 3:
输入:nums = [1] 输出:[[1]]提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums
中的所有整数 互不相同
题解输出该数组的所有排序组合,我们可以使用回溯法。首先确定一个位置,然后跟后面的每个位置进行交换。换完之后到下一个位置。然后这一系列步骤结束后,需要将换了的换回来。即回溯法。
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. 组合
题目
给定两个整数
n
和k
,返回范围[1, n]
中所有可能的k
个数的组合。你可以按 任何顺序 返回答案。
示例 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
题解
设定一个count,计算每一个的数量,当count==k时候,就放入数组。这是跟之前不太一样的,之前的是进行排列组合。这个有点像选择排列。
从1-n开始,设置一个额外的数组来存储每一次的结果。count动态变化,将i赋给后count加一,dfs中从(i+1,n)选一个数字。回溯后count--。
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. 单词搜索
题目
给定一个
m x n
二维字符网格board
和一个字符串单词word
。如果word
存在于网格中,返回true
;否则,返回false
。单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例 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+回溯法,首先定义一个visit,来标记每一次搜索的时候该位置是否被标记过,防止同一个位置被多次访问。
对于一个位置,要进行边界判断,是否越界。接着判断是否已经访问过,是否已经成功找到,是否该位置的字母与目标字母不同。
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 皇后
题目
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将
n
个皇后放置在n×n
的棋盘上,并且使皇后彼此之间不能相互攻击。给你一个整数
n
,返回所有不同的 n 皇后问题 的解决方案。每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中
'Q'
和'.'
分别代表了皇后和空位。示例 1:
输入:n = 4 输出:[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]] 解释:如上图所示,4 皇后问题存在两个不同的解法。示例 2:
输入:n = 1 输出:[["Q"]]提示:
1 <= n <= 9
题意
N皇后,需要三个标记函数,一个是列,一个是主对角线,另外一个是副对角线。
因为每一行肯定会放一个皇后,一行一行遍历,当成功遍历到最后一行并且成功放好皇后即可。所以不需要设行的标记函数。
这个时候我们可以从第一行开始,按列遍历。判断该列是否为false,该主对角线是否为false,副对角线是否为false。如果是则下一列,如果不是就将该位置置为Q,然后对下一行进行同样的寻找。回溯法,找完后记得将位置和标记函数还原。
这个对角线和副对角线。可以画在坐标上,一个为y=x+b,一个为y=-x+b。
所以b=y-x,为了使b>0,因此我们加上n。另外一个为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;}} };
总结
对于回溯法,首先找到边界条件以及结束的条件。一般为设置的i等于行数。
边界条件一般为不要越界。
一般还需要设置标记函数。然后一行一行进行访问或者一个位置一个位置的访问,访问过的标记函数置为true。接着继续下一个或者下一行(一般是递归)。然后结束后还原上面的标记函数以及board(一般会设置一个作为答案)。符合的就push_back到ans数组中去。