Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/22.html
Given n
pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Example 1:
Input: n = 3 Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2:
Input: n = 1 Output: ["()"]
Constraints:
1 <= n <= 8
Algorithm
To solve this problem, we can use a recursive approach, since the string contains only two types of characters: left and right parentheses, and the final result must have 3 left parentheses and 3 right parentheses. In this approach, we define two variables: left
and right
, which represent the number of left and right parentheses in the generated string.
During the recursive process, if the number of left parentheses is greater than the number of right parentheses, it means that the number of right parentheses in the generated string is greater than the number of left parentheses, which will result in an illegal string like )(
. In this case, we can return directly without further processing.
If both left
and right
are 0, it means that the generated string has 3 left brackets and 3 right parentheses, and the string is legal, so we can store it in the result and return.
If the above two conditions are not met, we can check if left
is greater than 0. If it is, we can call the recursive function and update the parameters accordingly. Similarly, if right
is greater than 0, we can call the recursive function and update the parameters.
Code
-
import java.util.ArrayList; import java.util.List; public class Generate_Parentheses { public class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<String>(); dfs(n, n, "", res); return res; } void dfs(int left, int right, String out, List<String> res) { if (left < 0 || right < 0 || left > right) return; if (left == 0 && right == 0) { res.add(out); return; } dfs(left - 1, right, out + "(", res); dfs(left, right - 1, out + ")", res); } } } ############ class Solution { private List<String> ans = new ArrayList<>(); private int n; public List<String> generateParenthesis(int n) { this.n = n; dfs(0, 0, ""); return ans; } private void dfs(int l, int r, String t) { if (l > n || r > n || l < r) { return; } if (l == n && r == n) { ans.add(t); return; } dfs(l + 1, r, t + "("); dfs(l, r + 1, t + ")"); } }
-
// OJ: https://leetcode.com/problems/generate-parentheses/ // Time: O(C(N)) where C(N) is the Nth Catalan number // Space: O(N) class Solution { private: vector<string> ans; void generate(int leftCnt, int rightCnt, string &s) { if (!leftCnt && !rightCnt) { ans.push_back(s); return; } if (leftCnt) { s.push_back('('); generate(leftCnt - 1, rightCnt, s); s.pop_back(); } if (rightCnt > leftCnt) { s.push_back(')'); generate(leftCnt, rightCnt - 1, s); s.pop_back(); } } public: vector<string> generateParenthesis(int n) { string s; generate(n, n, s); return ans; } };
-
class Solution: def generateParenthesis(self, n: int) -> List[str]: def dfs(l, r, t): if l > n or r > n or l < r: return if l == n and r == n: ans.append(t) return dfs(l + 1, r, t + '(') dfs(l, r + 1, t + ')') ans = [] dfs(0, 0, '') return ans ############ class Solution(object): def generateParenthesis(self, n): """ :type n: int :rtype: List[str] """ def dfs(left, path, res, n): if len(path) == 2 * n: if left == 0: res.append("".join(path)) return if left < n: path.append("(") dfs(left + 1, path, res, n) path.pop() if left > 0: path.append(")") dfs(left - 1, path, res, n) path.pop() res = [] dfs(0, [], res, n) return res
-
func generateParenthesis(n int) (ans []string) { var dfs func(int, int, string) dfs = func(l, r int, t string) { if l > n || r > n || l < r { return } if l == n && r == n { ans = append(ans, t) return } dfs(l+1, r, t+"(") dfs(l, r+1, t+")") } dfs(0, 0, "") return ans }
-
function generateParenthesis(n: number): string[] { function dfs(l, r, t) { if (l > n || r > n || l < r) { return; } if (l == n && r == n) { ans.push(t); return; } dfs(l + 1, r, t + '('); dfs(l, r + 1, t + ')'); } let ans = []; dfs(0, 0, ''); return ans; }
-
/** * @param {number} n * @return {string[]} */ var generateParenthesis = function (n) { function dfs(l, r, t) { if (l > n || r > n || l < r) { return; } if (l == n && r == n) { ans.push(t); return; } dfs(l + 1, r, t + '('); dfs(l, r + 1, t + ')'); } let ans = []; dfs(0, 0, ''); return ans; };
-
impl Solution { fn dfs(left: i32, right: i32, s: &mut String, res: &mut Vec<String>) { if left == 0 && right == 0 { res.push(s.clone()); return; } if left > 0 { s.push('('); Self::dfs(left - 1, right, s, res); s.pop(); } if right > left { s.push(')'); Self::dfs(left, right - 1, s, res); s.pop(); } } pub fn generate_parenthesis(n: i32) -> Vec<String> { let mut res = Vec::new(); Self::dfs(n, n, &mut String::new(), &mut res); res } }