括号生成--力扣

括号生成

• 前言
• 一、示例
• 二、代碼解析
• • 1.暴力解法
  • • 代碼如下（示例）：
    • 結果
  • 2.回溯法
  • • 代碼如下（示例）：
    • 結果
  • 測試
  • • 代碼如下（示例）：
    • 結果
• 總結

前言

數字 n 代表生成括号的對數，請你設計一個函數，用于能夠生成所有可能的并且 有效的 括号組合

一、示例

示例 1：

輸入：n = 3

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

示例 2：

輸入：n = 1

輸出：["()"]

提示：

1 <= n <= 8

二、代碼解析

1.暴力解法

代碼如下（示例）：

/// <summary>
/// 判斷目前是否是有效括号
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
bool valid(const string& str)
{
	int balance = 0;
	for (auto c : str)
	{
		if (c == '(')
		{
			++balance;
		}
		else
		{
			--balance;
		}
		if (balance < 0)
		{
			return false;
		}
	}
	return balance == 0;
}

/// <summary>
/// 生成所有括号排序可能
///	我們可以生成所有可能，然後檢查每一個是否是有效括号
/// </summary>
/// <param name="current"></param>
/// <param name="n"></param>
/// <param name="result"></param>
void generateAll(string& current, int n, vector<string>& result)
{
	if (n == current.size())
	{
		if (valid(current))
		{
			result.emplace_back(current);
		}
		return;
	}

	current += ")";
	generateAll(current, n, result);
	current.pop_back();
	current += "(";
	generateAll(current, n, result);
	current.pop_back();
}

vector<string> generateParenthesis(int n)
{
	vector<string> result;
	string currentStr;
	generateAll(currentStr, 2 * n, result);
	return result;
}
           

結果

2.回溯法

代碼如下（示例）：

//改進：如果左括号數量不大于 n，我們可以放一個左括号。如果右括号數量小于左括号的數量，我們可以放一個右括号。
void backtrack(string& cur, int n, vector<string>& ans, int open, int close)
{
	if (cur.size() == n * 2)
	{
		ans.push_back(cur);
		return;
	}
	if (open < n)
	{
		cur.push_back('(');
		backtrack(cur, n, ans, open+1, close);
		cur.pop_back();
	}
	if (close < open)
	{
		cur.push_back(')');
		backtrack(cur, n, ans, open, close+1);
		cur.pop_back();
	}
}

vector<string> generateParenthesis(int n)
{
	vector<string> result;
	string currentStr;
	backtrack(currentStr, n, result, 0, 0);
	return result;
}
           

結果

測試

代碼如下（示例）：

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

/*暴力解法
/// <summary>
/// 判斷目前是否是有效括号
/// </summary>
/// <param name="str"></param>
/// <returns></returns>
bool valid(const string& str)
{
	int balance = 0;
	for (auto c : str)
	{
		if (c == '(')
		{
			++balance;
		}
		else
		{
			--balance;
		}
		if (balance < 0)
		{
			return false;
		}
	}
	return balance == 0;
}

/// <summary>
/// 生成所有括号排序可能
///	我們可以生成所有可能，然後檢查每一個是否是有效括号
/// </summary>
/// <param name="current"></param>
/// <param name="n"></param>
/// <param name="result"></param>
void generateAll(string& current, int n, vector<string>& result)
{
	if (n == current.size())
	{
		if (valid(current))
		{
			result.emplace_back(current);
		}
		return;
	}

	current += ")";
	generateAll(current, n, result);
	current.pop_back();
	current += "(";
	generateAll(current, n, result);
	current.pop_back();
}*/
//改進：如果左括号數量不大于 n，我們可以放一個左括号。如果右括号數量小于左括号的數量，我們可以放一個右括号。
void backtrack(string& cur, int n, vector<string>& ans, int open, int close)
{
	if (cur.size() == n * 2)
	{
		ans.push_back(cur);
		return;
	}
	if (open < n)
	{
		cur.push_back('(');
		backtrack(cur, n, ans, open+1, close);
		cur.pop_back();
	}
	if (close < open)
	{
		cur.push_back(')');
		backtrack(cur, n, ans, open, close+1);
		cur.pop_back();
	}
}

vector<string> generateParenthesis(int n)
{
	vector<string> result;
	string currentStr;
	backtrack(currentStr, n, result, 0, 0);
	return result;
}

int main()
{
	vector<string> result = generateParenthesis(3);
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << " ";
	}
	return 0;
}
           

結果

總結