[LeetCode] 22. Generate Parentheses

轉自LeetCode

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

<Solution>

這題也是要求排列組合，直覺就用 DFS => 先求解，再回頭考慮其他情況

那 DFS 通常會用 recursive 的解法

判斷條件有

• 當左括號數目和右括號數目都為 0的時候，目前的字串是一組答案

• 只要左括號數目還不等於 0，就先處理左括號

• 右括號數目不等於 0，且還多於左括號數目 (不然會發生 ")(" 這種狀況)，處理右括號

code 如下

	class Solution {
	public:
	vector<string> generateParenthesis(int n) {
	vector<string> ans;
	//> use recursive
	recursive(n, n, "", ans);
	return ans;
	}
	void recursive(const int &open, const int &close, string curStr, vector<string> &ans) {
	//> all ( and ) are used
	if(open == 0 && close == 0) {
	ans.push_back(curStr);
	return;
	}
	//> still have (
	if(open > 0) {
	recursive(open-1, close, curStr+'(', ans);
	}
	//> still have ) and can be put after (
	if(close > 0 && close > open) {
	recursive(open, close-1, curStr+')', ans);
	}
	}
	};

view raw generateParentheses.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun generateParenthesis(n: Int): List<String> {
	val ans = mutableListOf<String>()
	dfs(n, n, "", ans)
	return ans
	}
	fun dfs(openCount: Int, closeCount: Int, cmb: String, ans: MutableList<String>) {
	if(openCount == 0 && closeCount == 0) {
	ans.add(cmb)
	return
	}
	if(openCount > 0) {
	dfs(openCount-1, closeCount, cmb + "(", ans)
	}
	if(closeCount > 0 && closeCount > openCount) {
	dfs(openCount, closeCount-1, cmb + ")", ans)
	}
	}
	}

view raw generate_parentheses.kt hosted with ❤ by GitHub