二刷代码随想录——回溯day30

本文主要是介绍二刷代码随想录——回溯day30，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

前言

一个本硕双非的小菜鸡，备战24年秋招，计划二刷完卡子哥的刷题计划，加油！
二刷决定精刷了，于是参加了卡子哥的刷题班，训练营为期60天，我一定能坚持下去，迎来两个月后的脱变的，加油！
推荐一手卡子哥的刷题网站，感谢卡子哥。代码随想录

回溯法知识点

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯 (opens new window)。

回溯是递归的副产品，只要有递归就会有回溯。

回溯法的效率

回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

回溯法模板

void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

一、今天压力山大，先跳过332.重新安排行程

77. 组合
Note：回溯法（非剪枝）

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(int n, int k, int startIndex) {if (path.size() == k) {result.push_back(path);return;}for (int i = startIndex; i <= n; i++) {path.push_back(i);backtracking(n, k, i + 1);path.pop_back();}}
public:vector<vector<int>> combine(int n, int k) {result.clear();path.clear();backtracking(n, k, 1);return result;}
};

二、51. N 皇后

51. N 皇后
Note：一刷时候唯一看懂的一道回溯困难

class Solution {
private:vector<vector<string>> result;void backtracking(int n, int row, vector<string>& chessboard) {if (row == n) {result.push_back(chessboard);return;}for (int col = 0; col < n; col++) {if (isValid(row, col, chessboard, n)) {chessboard[row][col] = 'Q';backtracking(n, row + 1, chessboard);chessboard[row][col] = '.';}}}bool isValid(int row, int col, vector<string>& chessboard, int n) {/*检查列*/for (int i = 0; i < row; i++) {if (chessboard[i][col] == 'Q')return false;}/*检查↗*/for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (chessboard[i][j] == 'Q')return false;}/*检查↖*/for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (chessboard[i][j] == 'Q')return false;}return true;}
public:vector<vector<string>> solveNQueens(int n) {result.clear();vector<string> chessboard(n, string(n, '.'));backtracking(n, 0, chessboard);return result;}
};

三、37. 解数独

37. 解数独
Note：印象极为深刻的回溯

class Solution {
private:bool backtracking(vector<vector<char>>& board) {for (int i = 0; i < board.size(); i++) {for (int j = 0; j < board[0].size(); j++) {if (board[i][j] != '.') continue;for (char k = '1'; k <= '9'; k++) {if (isValid(i, j, k, board)) {board[i][j] = k;if (backtracking(board)) return true;board[i][j] = '.';}}return false;}}return true;}bool isValid(int row, int col, char val, vector<vector<char>>& board) {/*行判断*/for (int i = 0; i < 9; i++) {if (board[row][i] == val) {return false;}}/*列判断*/for (int j = 0; j < 9; j++) {if (board[j][col] == val) {return false;}}int startRow = (row / 3) * 3;int startCol = (col / 3) * 3;/*九宫格判断*/for (int i = startRow; i < startRow + 3; i++) {for (int j = startCol; j < startCol + 3; j++) {if (board[i][j] == val)return false;}}return true;
}
public:void solveSudoku(vector<vector<char>>& board) {backtracking(board);}
};

总结

回溯法解决的问题都可以抽象为树形结构，因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

这篇关于二刷代码随想录——回溯day30的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---