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

// N 皇后问题 leetcode 51 https://leetcode-cn.com/problems/n-queens/
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 column=0; column < n; column++){ // 每一行都有8中放法
 if (isOK(row, column, n, chessboard)){
                chessboard[row][column] = 'Q'; // 放置皇后
 backtracking(n, row+1, chessboard);
                chessboard[row][column] = '.'; // 回溯，撤销处理结果
 }
 }
 }
 // 判断 row 行 column 列放置皇后是否合适
    bool isOK(int row, int column, int n, vector<string>& chessboard){
        int leftup = column - 1; int rightup = column + 1; // 左上角和右上角
 for(int i = row-1; i>=0; i--){ // 逐行网上考察每一行
 // 判断第 i 行的 column 列是否有棋子
 if(chessboard[i][column] == 'Q') {
 return false;
 }
 // 考察左上对角线：判断第i行leftup列是否有棋子 
 if(leftup >=0 ){
 if(chessboard[i][leftup] == 'Q') return false;
 }
 // 考察左上对角线：判断第i行rightup列是否有棋子
 if(rightup < n){
 if(chessboard[i][rightup] == 'Q') return false;
 }
 --leftup;
 ++rightup;
 }
 return true;
 } 
public:
    vector<vector<string>> solveNQueens(int n) {
 result.clear();
 std::vector<std::string> chessboard(n, std::string(n, '.'));
 backtracking(n, 0, chessboard);
 return result;
 }
};

int maxW = 0;
// cw 表示当前装进背包的物品的重量和，w 表示背包承载的重量
// items  表示物体的重量数组，n 表示总的物品个数， i 表示考察到第 i 个物品
int f(int i, int cw, vector<int> items, int n, int w){
 // 递归结束条件：cw == w 表示背包已经装满，i==n 表示考察完所有物品
 if(cw == w || i == n){
 if(cw > maxW) maxW = cw;
 return;
 }
 f(i+1, cw, items, n, w); // 不装
 // 剪枝过程，当装入的物品重量大于背包的重量，就不继续执行
 if(cw+items[i] <= w){
 f(i+1, cw+items[i], items, n, w); // 装
 }
}

// 暴力递归 --> 记忆化 --> DP --> 状态压缩DP；
class Solution{
private:
    bool matched = false;
 void backtracking(int ti, int pj, string text, string pattern){
 if (matched) return;
 if(pj == pattern.size()){ // 正则表达式到末尾了
 if(ti == text.size())
                matched = true;
 return;
 }
 // *匹配任意个字符
 if(pattern[pj] == '*'){
 for(int k=0; k< text.size()-ti;k++)
 backtracking(ti+k, pj+1, text, pattern);
 }
 // ?匹配0个或者1个字符
 else if(pattern[pj] == '?'){
 backtracking(ti, pj+1, text, pattern);
 backtracking(ti+1, pj+1, text, pattern);
 }
 // 纯字符匹配才行 
 else if(ti < pattern.size() && pattern[pj] == text[ti]) { 
 backtracking(ti+1, pj+1, text, pattern);
 }
 }
public:
    bool isMatch(string text, string pattern){
        matched = false;
 backtracking(0, 0, text, pattern);
 return matched;
 }
};

def isMatch(self,s:str, p:str) -> bool:
 """字符串 s 和字符规律 p"""
 if not p: return not s # 边界条件
 first_match = s and p[0] in {s[0],'.'} # 比较第一个字符是否匹配
 return first_match and self.isMatch(s[1:], p[1:])

class Solution:
 def isMatch(self, s: str, p: str) -> bool:
 if not p: return not s
 first_match = bool(s and p[0] in {s[0],'.'}) # 比较第一个字符是否匹配
 if len(p) >=2 and p[1] == '*':
 # * 匹配前面一个字符 0 次或者多次
 return self.isMatch(s, p[2:]) or first_match and self.isMatch(s[1:], p)
 else:
 return first_match and self.isMatch(s[1:], p[1:])

// letcode10 正则表达式匹配
#include <vector>
#include <string>
using namespace std;
class Solution{
public:
    bool isMatch(string s, string p){
 // 如果正则串 p 为空字符串，s 也为空，则匹配成功
 if(p.empty()) return (s.empty());
 // 判断 s 和 p 的首字符是否匹配，注意要先判断 s 不为空
        bool match = (!s.empty()) && (s[0] == p[0] || p[0] == '.');
 // 如果p的第一个元素的下一个元素是 *，则分别对两种情况进行判断
 if(p.size() >= 2 && p[1] == '*'){
 // * 匹配前面一个字符 0 次或者多次
 return isMatch(s, p.substr(2)) || (match && isMatch(s.substr(1), p));
 }
 else{ // 单个匹配
 return match && isMatch(s.substr(1), p.substr(1));
 }
 }
};

class Solution{
public:
    bool isMatch(string s, string p){
 unordered_map<int, bool> memo;
 return backtracking(s, 0, p, 0, memo);
 }
    bool backtracking(string s, int i, string p, int j, unordered_map<int, bool> & memo){
 // # 检查 s[i] 是否能被匹配，注意要先判断 s 不为空
        bool match = (i < s.size()) && (s[i] == p[j] || p[j] == '.');
 if(j >= p.size()) return i >= s.size(); // p 和 s 同时遍历完
        int key = i * (p.size() + 1) + j; // 哈希键
 if (memo.find(key) != memo.end()) // 这个状态之前经历过，可以返回结果
 return memo[key];
 else if (i == s.size() && j == p.size()) // 如果s和p同时用完，匹配成功
 return memo[key] = true;
 else if((p.size()-j) >= 2 && p[j+1] == '*'){
 // * 匹配前面一个字符 0 次或者多次
 if(backtracking(s, i, p, j+2, memo) || match && backtracking(s, i+1, p, j, memo))
 return memo[key] = true;
 }
 else { // 单个匹配
 if(match && backtracking(s, i+1, p, j+1, memo))
 return memo[key] = true;
 }
 return memo[key] = false; // 没辙了，匹配失败
 }
};