系统会为您提供n对括号，并生成格式正确的括号的所有组合。

例如，给定 n = 3，国彩网解决方案集是：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

这个问题可以通过许多不同的方式解决。其中一些包括“ DFS”，“ BFS”，“回溯”，“动态编程”，“递归”。

在本教程中，我们将考虑“递归”解决方案。如果您需要其他解决方法的帮助，请告诉我。我将尽力提供相同的内容。

首先，什么是递归？

调用自身的函数称为递归。我们知道。许多程序员使用递归，因为它可以使代码可读并且占用更少的空间。但是同时，许多面孔在可视化上都存在困难。

根据以上定义，调用自身的函数是递归函数。但是此时您可能会感到怀疑。如果国彩网函数本身正在调用，它什么时候停止？如果您在某个点连续不断地单独调用国彩网函数，则会出现“ SystemStackError”或“ stack stackover”错误。

检查何时停止递归的条件称为 基本条件.

因此，我们将借助国彩网示例来理解这一点：

考虑国彩网生成数字阶乘的程序。我们将通过递归来解决它。

该函数的伪代码如下：

int factorial(int num)
{
    if (num >= 1)
        return n* factorial (num - 1);
    else if (num == 1) // 基本条件
        return 1;
}

使用上面的伪代码，我们尝试获得阶乘为5。

factorial(5) = 5 * factorial(4)
factorial(4) = 5 * 4 * factorial(3)
factorial(3) = 5 * 4 * 3 * factorial(2)
factorial(2) = 5 * 4 * 3 * 2 * factorial(1)
factorial(1) = 5 * 4 * 3 * 2 * 1 // reached 基本条件.
= 120

因此，基于以上理解，我们将着手解决括号问题。

解决方法是保持一对一地加上开括号和闭括号。我们通过使用2个变量left_parentheses和right_parentheses来跟踪它们。

步骤如下：

第1步： 使用left_parentheses = n的数量调用递归函数。

第2步： 每当我们添加左括号时，我们都会减小left_parentheses并增加right_parentheses。这是为了平衡左右括号。我们这样做直到没有左括号被添加。

第三步： 如果right_parentheses的值>= 1，我们应添加右括号并减小right_parentheses的值。 left_parentheses值应相同。

步骤4： [基本情况]。如果right_parentheses和left_parentheses都等于0，那么我们将该字符串添加到结果集中。

Pseudo code:

void recursive_function (vector<string> &final_result, string temp_str, int left_parentheses , int right_parentheses)
{
    if( left_parentheses == 0 && right_parentheses == 0) 
    {
        final_result.push_back(temp_str);
        return;
    }

    if(left_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+"(", left_parentheses -1, right_parentheses +1); 
    }
        
    if(right_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+")", left_parentheses , right_parentheses - 1); 
    }

我们来看国彩网例子：

When n = 1 
n = 1

Pass 1:
	left_parentheses = 1
	right_parentheses = 0
	temp_string = ""

	Hence left_parentheses > 0, add "(" to temp string, decrement left_parentheses and increment right_parentheses, call recursive funtion.

Pass 2:
	left_parentheses = 0
	right_parentheses = 1
	temp_string = "("
	Hence right_parentheses > 0, add ")" to temp string, decrement right_parentheses and leave left_parentheses, call recursive funtion.

Pass 3:
	left_parentheses = 0
	right_parentheses = 0
	temp_string = "()"

As both "left_parentheses" and "left_parentheses" equal to 0. We add it to result set.

因此，遵循相同的顺序，我们可以求解“ n = 3”。

C ++中的解决方案：

#include<iostream>
#include<vector>
using namespace std;


void recursive_function (vector<string> &final_result, string temp_str, int left_parentheses , int right_parentheses)
{
    if( left_parentheses == 0 && right_parentheses == 0) 
    {
        final_result.push_back(temp_str);
        return;
    }

    if(left_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+"(", left_parentheses -1, right_parentheses +1); 
    }
        
    if(right_parentheses > 0)
    { 
        recursive_function(final_result, temp_str+")", left_parentheses , right_parentheses - 1); 
    }


}


vector<string> generateParenthesis(int n) 
{
    vector<string> final_result;

    recursive_function(final_result, "", n, 0);
    
    return final_result;
}

int main() 
{
    
    vector<string> final_result ;
    int n = 3;

    final_result = generateParenthesis(n);

    for (int j = 0; j < final_result.size(); j++)
                cout << final_result[j] << endl;

}

输出：

((()))
(()())
(())()
()(())
()()()

该网站上可用的教程列表：