[LeetCode] 022. Generate Parentheses (Medium) (C++/Python)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)Github: https://github.com/illuz/leetcode

022.Generate_Parentheses (Medium)链接：

题目：https://oj.leetcode.com/problems/generate-parentheses/代码(github)：https://github.com/illuz/leetcode

题意：

产生有 n 对括号的所有有效字符串。

分析：代码：

C++:

class Solution {private:string tmp;void dfs(vector<string> &v, int pos, int n, int used) {if (pos == n * 2) {cout << tmp << endl;v.push_back(tmp);return;}if (used < n) {tmp.push_back('(');dfs(v, pos + 1, n, used + 1);tmp.pop_back();}if (used * 2 > pos) {tmp.push_back(')');dfs(v, pos + 1, n, used);tmp.pop_back();}}public:vector<string> generateParenthesis(int n) {vector<string> res;if (n == 0)return res;tmp = "";dfs(res, 0, n, 0);return res;}};

Java:

public class Solution {public List<String> generateParenthesis(int n) {List<String> ret = new ArrayList<String>(), inner, outter;if (n == 0) {ret.add("");return ret;}if (n == 1) {ret.add("()");return ret;}for (int i = 0; i < n; ++i) {inner = generateParenthesis(i);outter = generateParenthesis(n – i – 1);for (int j = 0; j < inner.size(); ++j) {for (int k = 0; k < outter.size(); ++k) {ret.add("(" + inner.get(j) + ")" + outter.get(k));}}}return ret;}}

Python:

class Solution:# @param an integer# @return a list of stringdef generateParenthesis(self, n):dp = {0: [""], 1: ["()"]}def memorial_dfs(n):if n not in dp:dp[n] = []for i in range(n):for inner in memorial_dfs(i):for outter in memorial_dfs(n – i – 1):dp[n].append('(' + inner + ')' + outter)return dp[n]return memorial_dfs(n)

，放弃等于又一次可以选择的机会。