带约束条件树（减枝）的使用练习

带约束条件树（减枝）的使用练习

递归，回溯，递推

在算法处理中，递归实现比较方便，有些像责任链的处理方式，一层层的去处理复杂的流程。

下面的例子比较经典，

22. 括号生成

力扣

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1

输出：["()"]

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/generate-parentheses

对于这样的问题，需要观察找到一些规律，比如合法的括号匹配应该是从头开始的任意长度中，左括号的数量应该大于大于右括号的数量。

画图看一下，褐色是左括号，青色是右括号，

在二叉树的基础上加上条件，左括号数量大于等于右括号数量，就可以画出树结构，

再输出叶子节点路径，即为所求答案。

递归的实现：

class Solution {

public:

    vector ret;

    vector tmp;

    void get(int l, int r, int n) {

        if (r == n) {

            string t = "";

            for (int i = 0; i < tmp.size(); i++) {

                if (tmp[i] == 0) t.append("(");

                else t.append(")");

            }

            ret.push_back(t);

            return;

        }

        //add (

        if (l < n) {

            tmp.push_back(0);

            get(l+1, r, n);

            tmp.pop_back();

        }

        //add )

        if (r < n && l > r) {

            tmp.push_back(1);

            get(l, r+1, n);

            tmp.pop_back();

        }

    }

    vector generateParenthesis(int n) {

        if (n == 1) {

            ret.push_back("()");

            return ret;

        }

        tmp.push_back(0);

        get(1, 0, n);

        return ret;

    }

};

还可以通过递推来实现，找到前后2次的递推规律。