leetcode-22：括号生成的深度优先搜索+剪枝解法分析

本文主要是介绍leetcode-22：括号生成的深度优先搜索+剪枝解法分析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]

题目是括号生成，也就是最终用一个数据结构保存所有可能的有效字符串。每一个字符串的生成过程，都必然是放入了2n个括号，或者说选择2n次，每次要么选 "(" 要么选 ")" ，类似二叉树，那么最简单暴力的办法就是找出每一种选择生成方式，然后遍历每一种方式看是否有效，有效进数组，无效抛弃。这种方法的时间复杂度非常高。很明显暴力法存在大量的无效解，对于这种情况，通常可以采用动态规划，回溯或剪枝的思想来解决。这里考虑用深度优先搜索和剪枝。
括号的生成过程，可以对应一颗二叉树的建立或者遍历过程。

• 暴力法是建立了一颗满二叉树，然后逐个筛选有效的；

• 观察二叉树的剪枝操作，条件很显然当x>0时就能往左走，只有x<y的时候才能往右走
  括号生成的原理：

  1. x>0就能往左走：因为只要还能放左括号，那么往字符串里再放一个左括号，字符串仍有成功匹配的可能；
  2. x<y才能往右走：隐含条件y>0，剩余的左括号更少，字符串里的左括号就更多，此时放右括号仍有匹配成功的可能性，反之，再放一个右括号立马不匹配了。
     推出了限制条件，就容易想到带条件的DFS的算法，在遍历二叉树的同时判断出不需要的节点,递归的代码

class Solution
{
  public:
    //定义一个全局的向量作为最后的输出和中间修改过程的容器
    vector<string> ans;
    vector<string> generateParenthesis (int n)
    {
        dfs(n, n, "");
        return ans;
    }
    // DFS，left表示还需要放入的左括号数量，right同理,left和right都不剩余，则str就绪
    void dfs (int left, int right, string str)
    {
        if (left == 0 && right == 0) {  //括号都放完了，str压入结果数组，返回上一层递归函数
            ans.push_back(str);
            return;
        }
        // 1.左括号还有，压入递归栈
        if (left > 0)
            dfs(left - 1, right, str + "(");
        // 2.剩余右括号比剩余左括号多，压入递归栈
        if (right > left)
            dfs(left, right - 1, str + ")");
    }
};

这篇关于leetcode-22：括号生成的深度优先搜索+剪枝解法分析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！