medium
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:
[ "((()))", "(()())", "(())()", "()(())", "()()()" ]
- when both left and right are used up, we add to result.
- Watch return cases! if left > right, no valid answer. eg: )(())(
Also we can't have > n left or right bracket
Complexity: Time O(2^n) Space O(n)
public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<String>(); dfs(new StringBuilder(), n, n,res); return res; } public void dfs(StringBuilder path,int left,int right,List<String> res){ int len = path.length(); if(left > right || left < 0 || right < 0){ return; } if(left == 0 && right == 0){ res.add(path.toString()); return; } dfs(path.append("("),left-1,right,res); path.setLength(len); dfs(path.append(")"),left,right-1,res); path.setLength(len); }
No comments:
Post a Comment