【递归】 LeetCode22. 括号生成

布满荆棘的人生 2022-12-03 05:21 172阅读 0赞

### 题目 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]

### 解答 ###

> 回溯法的求解过程实质上是一个先序遍历一棵状态树的过程，只是这棵树不是遍历前预先建立的，而是隐含在遍历的过程中。

> 递归题的解法：首先把题目的决策树画出来，树的层就是for循环，树的深度就是要递归的参数i。画出决策树后，找规律，进行剪枝。

**E.g.** 输入 n = 3

树的层为左括号或者右括号，树的深度为括号的个数。  
排序后用set去重。

左括号为3个，右括号为3个。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]

### 代码 ###

#include <iostream>
    #include <string>
    #include <list>
    #include <vector>
    #include <map>
    #include <utility>
    #include <functional>
    #include <algorithm>
    #include <set>
    #include <cassert>
    
    // 22. Generate Parentheses
    
    // 本质：一棵二叉树递归遍历的变形。 
    
    void Func(int i, int n, int left, int right, std::string str, std::vector<std::string>& result) { 
      if (left < right) { 
        return;
      }
    
      if (i >= n) { 
        if (left == right) { 
          result.push_back(str);
        }
        return;
      }
    
      Func(i + 1, n, left + 1, right, str + "(", result);
      Func(i + 1, n, left, right + 1, str + ")", result);
    }
    
    std::vector<std::string> generateParenthesis(int n) { 
      std::vector<std::string> result;
      Func(0, 2 * n, 0, 0, "", result);
    
      return result;
    }
    
    void PrintResult(const std::vector<std::string>& result) { 
      for (const auto& str : result) { 
        std::cout << str << std::endl;
      }
    }
    
    int main() { 
      PrintResult(generateParenthesis(3));
    
      return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/ad19fbca278944c490133659b92c3f2b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE3MjYwMDU_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/682437063b004330b7d416ff93b9df3d.png