之后的日子，大概会放缓刷题的脚步进行简单的整理，因为有些题目是有规律的，需要做号总结和整理，不能刷一个忘一个。今日总结：题目要求返回所有结果，且能找到分界点分解为子问题的，都可以套用分治枚举算法。

分治算法枚举

众所周知，枚举是个技术活，如何合理的枚举所有结果、避免重复和剪枝，并没有想象的那么简单。而分治枚举就是，通过将原问题分割为多个子问题，多个子问题的解排列组合能产生多种答案，我们收集多种答案并返回。

对于此类问题，我们需要确定三个东西：分界点，递归函数，如何排列组合。这样，给定一个分界点，我们把问题分解为左侧问题和右侧问题，两者答案的组合就是当前分界点对应的所有结果。然后再移动分界点，得到其他所有结果即可。此外，再分割得到子问题并求解时，需要设置 base case 用于退出递归。

96. 不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的二叉搜索树有多少种？返回满足题意的二叉搜索树的种数。如下的示例，3 个节点能组成 5 种二叉树。

那我们考虑给出那三个东西：

分界节点，以不同的值作为根节点，遍历所有的情况
既然有了根节点，就需要构建左子树。定义一个函数，返回某子树对应的情况，也就能得到分界点左子树有多少情况，同理得到右子树的排列组合
而左子树和右子树的乘积就是当前根节点对应的结果

我们定义一个函数，函数有两个参数，这两个参数是子树的取值范围，因此，退出递归的 base case 就是子树的左侧值大于右侧值，此时返回 1，因为表示调用者的结果是 1，不能再划分为子问题了。函数的返回值是这种取值范围下，有多少结果。我们写出程序：

class Solution {
public:
    int res = 0;
    vector<vector<int>> memo;
    int numTrees(int n) {
        vector<vector<int>> tmp(n, vector<int>(n, 0));
        memo = tmp;
        return build(1, n);
    }

    int build(int l, int r) {
        // base case
        if (l > r)
            return 1;
        if (memo[l-1][r-1] != 0)
            return memo[l-1][r-1];
        for (int i = l; i <= r; i++) {
            int a = build(l, i - 1);
            int b = build(i + 1, r);
            // 累积所有的结果
            memo[l-1][r-1] += a*b;
        }
        return memo[l-1][r-1];
    }
};

其中，memo 起到剪枝的效果。

95. 不同的二叉搜索树 II

1 2	输入：n = 3 输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

同上一题，既然要给出所有的子树结果，那么此时就不需要计数，而是需要创建子树。同样以根节点的取值为分界点，统计出所有可能的左子树，统计出所有可能的右子树，上一题为结果相加，那么这个题目需要对左右子树的结果进行排列组合。因为这题不会超时，因此没有设置剪枝。

vector<TreeNode*> build(int l, int r) {
    if (l > r) {
        return {nullptr};
    }
    vector<TreeNode*> res;
    for (int i = l; i <= r; i++) {
        auto leftTree = build(l, i - 1);
        auto rightTree = build(i + 1, r);
        // 创建子树，等价于上一题的相加
        for (auto a : leftTree) {
            for (auto b : rightTree) {
                TreeNode* node = new TreeNode(i);
                node->left = a;
                node->right = b;
                res.emplace_back(node);
            }
        }
    }
    return res;
}

241. 为运算表达式设计优先级

给你一个由数字和运算符组成的字符串 expession ，按不同优先级组合数字和运算符，计算并返回所有可能组合的结果。你可以按任意顺序返回答案。

输入：expression = "2*3-4*5"
输出：[-34,-14,-10,-10,10]
解释：
(2*(3-(4*5))) = -34 
((2*3)-(4*5)) = -14 
((2*(3-4))*5) = -10 
(2*((3-4)*5)) = -10 
(((2*3)-4)*5) = 10

最开始我以为这是回溯，后来发现不是，因此总结出一个规律：题目要求返回所有结果，且能找到分界点分解为子问题的，都可以套用分治枚举算法。对于这个题而言，运算符就是分界点，然后枚举左侧和右侧有几种结果即可。

vector<int> diffWaysToCompute(string expression) {
    vector<int> res;
    for (int i = 0; i < expression.size(); i++) {
        if (expression[i] == '-' || expression[i] == '*' || expression[i] == '+') {
            // 分治，左侧有几种结果
            auto res1 = diffWaysToCompute(expression.substr(0, i));
            auto res2 = diffWaysToCompute(expression.substr(i + 1));
            // 枚举所有结果，并追加，和第一题的 += 一样
            for (auto it1 : res1) {
                for (auto it2 : res2) {
                    if (expression[i] == '-')
                        res.push_back(it1 - it2);
                    if (expression[i] == '+')
                        res.push_back(it1 + it2);
                    if (expression[i] == '*')
                        res.push_back(it1 * it2);
                }
            }
        }
    }
    if (res.size() == 0) {
        return {stoi(expression)};
    }
    return res;
}

Just for Life.

算法系列：分治枚举

分治算法枚举

96. 不同的二叉搜索树

95. 不同的二叉搜索树 II

241. 为运算表达式设计优先级