GeetCode Hub

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

class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<String>(); if(n<=0){ return res; } int open = 0; int close = 0; generateParenthesis(n, open, close, "",res); return res; } private void generateParenthesis(int n, int open, int close, String asf, List<String> res){ if(open == n && close == n){ res.add(asf); return; } if(open > n || close > n){ return; } generateParenthesis(n, open+1, close, asf+"(", res); if(open>close){ generateParenthesis(n, open, close+1, asf+")", res); } } }

This question is a good example of Recursion with Backtracking. if you know how we can leverage the concept of backtracking then it will be an easy question to be solved.

Time Complexity: O(2^n)

Space Complexity: O(n)