LeetCode [22] Generate Parentheses

 22. Generate Parentheses

Medium

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; if(!n) return res; bt(res, n*2, "", 0, 0, 0); } void bt(vector<string> &res, int n, string cur, int pos, int nl, int nr){ if(pos==n){ res.push_back(cur); }else{ if(nl>nr) bt(res, n, cur+")", pos+1, nl, nr+1); if(nl<n/2) bt(res, n, cur+"(", pos+1, nl+1, nr); } } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

class Solution { List<String> list = new ArrayList<>(); public List<String> generateParenthesis(int n) { helper(n, "", 0, 0); return list; } void helper(int n, String cur, int left, int right){ if(cur.length()==2*n){ list.add(cur); }else{ if(left<n){ helper(n, cur+"(", left+1, right); if(right<left) helper(n, cur+")", left, right+1); }else{ helper(n, cur+")", left, right+1); } } } }