Leetcode算法基础篇-回溯算法

回溯算法

回溯算法（Backtracking）：一种能避免不必要搜索的穷举式的搜索算法。采用试错的思想，在搜索尝试过程中寻找问题的解，当探索到某一步时，发现原先的选择并不满足求解条件，或者还需要满足更多求解条件时，就退回一步（回溯）重新选择，这种走不通就退回再走的技术称为「回溯法」，而满足回溯条件的某个状态的点称为「回溯点」。

核心思想：不断试错！

解题思路：

• 明确所有可能的选择：画出搜索过程的决策树，根据决策确定搜索的方向和路径
• 优化：搜索过程可能的剪枝
• 明确搜索结束条件：判定出什么时间结束，以及结束时的处理方法
• 实现为代码

伪代码：

ans = []
curr = []
def backtracking(choices):if stop_condition:ans.append(curr[:])returnfor choice in choices:cur.append(choice)backtraccking(choices)cur.pop()

练习题

78. 子集

思路

• 我们考虑分为多个子搜索，每个搜索负责生成指定长度的子集
• 对于每个子搜索，枚举所有的不重复数据组合，注意每次从nums中开始的顺序
• 搜索。

代码

class Solution {
public:vector<vector<int>> ans = {{}};void dfs(vector<int>& nums, vector<int>& cur, int n, int d) {if(cur.size() == n) {ans.push_back(cur);return;}for(int i = d; i < nums.size(); ++i) {cur.push_back(nums[i]);dfs(nums, cur, n, i + 1);cur.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {int sz = nums.size();if(sz == 0) return {};if(sz == 1) return {{}, nums};ans.push_back(nums);vector<int> cur;for(int n = 1; n < sz; n++) {dfs(nums, cur, n, 0);}return ans;}
};

51. N 皇后

思路

• 我们生成一个空棋盘，每次逐行放一个皇后
• 对于每次要放置皇后的位置，我们要判断是否合理
  • 判断同列是否有其他皇后
  • 判断正对角线是否有其他皇后
  • 判断反对角线是否有其他皇后
  • 如果都没有，则可以放置，否则不行
• 放置皇后，继续棋盘下一行，直至完成一个完整棋盘填充

代码

class Solution {
public:vector<vector<string>> ans;void dfs(vector<string>& board, int row) {int n = board.size();if(row == n) {ans.push_back(board);return;}for(int col = 0; col < n; col++) {if(!isValid(board, row, col)) continue;board[row][col] = 'Q';dfs(board, row + 1);board[row][col] = '.';}}bool isValid(vector<string>& board, int row, int col) {for(int i = 0; i < row; ++i) {if(board[i][col] == 'Q') return false;}int n = board.size();for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if(board[i][j] == 'Q') return false;}for(int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if(board[i][j] == 'Q') return false;}return true;}vector<vector<string>> solveNQueens(int n) {vector<string> board(n, string(n, '.'));dfs(board, 0);return ans;}
};