Sunday, November 1, 2015

Zenefits: Generate Parentheses

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:
"((()))", "(()())", "(())()", "()(())", "()()()"
Code (Java):
public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        
        if (n <= 0) {
            return result;
        }
        
        StringBuffer sb = new StringBuffer();
        
        generateParenthesisHelper(0, 0, n, sb, result);
        
        return result;
    }
    
    private void generateParenthesisHelper(int left, int right, int n, 
        StringBuffer sb, List<String> result) {
        if (left < right) {
            return;
        }
        
        if (left == n && right == n) {
            result.add(sb.toString());
            return;
        }
        
        if (left < n) {
            sb.append("(");
            generateParenthesisHelper(left + 1, right, n, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }
        
        if (right < n) {
            sb.append(")");
            generateParenthesisHelper(left, right + 1, n, sb, result);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

No comments:

Post a Comment