Skip to content

Instantly share code, notes, and snippets.

@b27lu
Created February 12, 2014 19:00
Show Gist options
  • Save b27lu/8962205 to your computer and use it in GitHub Desktop.
Save b27lu/8962205 to your computer and use it in GitHub Desktop.
Generate Parentheses @ LeetCode
public class Solution {
public ArrayList<String> generateParenthesis(int n) {
ArrayList<String> result = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
if(n <= 0)
return result;
dfsWorker(n, result, sb, 0, 0);
return result;
}
public void dfsWorker(int n, ArrayList<String> result, StringBuilder sb, int left, int right){
//"exit" for recursive call
if(left == right && right == n){
result.add(sb.toString());
return;
}
//invalid combination
if(left < right || left > n || right > n)
return;
//condition that add '('
if(left < n){
sb.append('(');
dfsWorker(n, result, sb, left+1, right);
sb.deleteCharAt(sb.length()-1);
}
//condition that add ')'
if(right < left){
sb.append(')');
dfsWorker(n, result, sb, left, right+1);
sb.deleteCharAt(sb.length()-1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment