1. 八皇后

class Solution {
private:
    vector<vector<string>> ans;
    vector<string> curr;
    void recursion(int i, int n) {
        // 1.终止条件
        if (i >= n) {
            ans.push_back(curr); //将当前解法加入结果中
        } 

        // 2.当前处理
        // 2.1 遍历所有列
        for (int j=0; j<n; ++j) {
            // 2.2 对于满足条件的列加入curr并且递归调用下一行，结束时回溯
            if (isOk(i, j, n)) {
                string temp(n, .);
                temp[j] = Q;
                curr.push_back(temp);
                recursion(i+1, n);
                curr.pop_back();
            }
        }
    }

    // 判断[i,j]放置是否和之前的放置curr冲突
    bool isOk(int i, int j, int n) {
        // 由下往上遍历curr
        for (int k=i-1; k>=0; --k) {
            // 1.不能同列
            if (Q == curr[k][j]) return false;

            // 2.左上对角线不能冲突，注意边界
            int left_up = j - (i-k);
            if (left_up >= 0 && Q == curr[k][left_up]) return false;

            // 3.右上对角线不能冲突，注意边界
            int right_up = j + (i-k);
            if (right_up < n && Q == curr[k][right_up]) return false;
        }
        return true; //不冲突
    }
public:
    vector<vector<string>> solveNQueens(int n) {
        // 1.处理
        recursion(0, n);
        // 2.返回结果
        return ans;
    }
};

空间复杂度O(n*n)，时间复杂度O(n!)

2. 背包问题

leetcode相关题目：

416 分割等和子集（medium） 494 目标和（medium） 474 一和零（medium） 322 零钱兑换（medium） 518 零钱兑换 II（medium） 139 单词拆分（medium） 377 组合总和 Ⅳ（medium）

2.1 0-1背包

可以使用回溯，虽然不是最好的解决办法

2.2 0-1背包改造版

2.3 分割等和子集

3. 正则表达式

4. 深度优先搜索

5. 图的着色

6. 旅行商问题

7. 数独

8. 全排列