Friday, January 17, 2014

Leetcode: Generate Parenthesis

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

Solution:

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> solution = new ArrayList<String>();
        generateParenthesis(n, 0, 0, new StringBuilder(), solution);
        return solution;
    }
    
    public void generateParenthesis(int n, int openParentheses, int closeParentheses, StringBuilder sb, List<String> solution)
    {
        if(closeParentheses == n)
        {
            solution.add(sb.toString());
        }
        if(openParentheses<n)
        {
            sb.append('(');
            generateParenthesis(n, openParentheses+1, closeParentheses, sb, solution);
            sb.deleteCharAt(sb.length()-1);
        }
        if(closeParentheses<openParentheses)
        {
            sb.append(')');
            generateParenthesis(n, openParentheses, closeParentheses+1, sb, solution);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

No comments :

Post a Comment