Question9_6.java

import java.util.LinkedList;

/**
 * Implement an algorithm to print all valid (i.e., properly opened and closed) combinations of n-pairs of parentheses.
 *  
 * Time  Complexity: O(2^n)
 * Space Complexity: O(2^n)
 */

public class Question9_6 {
    public LinkedList<String> parentheses(int n) {
        LinkedList<String> parentheses = new LinkedList<String>();
        recParentheses(parentheses, n, 0, 0, new StringBuffer());
        return parentheses;
    }
    
    
    private void recParentheses(LinkedList<String> parentheses, int n, int left, int right, StringBuffer parenthese) {
        if (n <= left && n <= right) {
            parentheses.add(parenthese.toString());
            return;
        }
        
        if (left < n) {
            parenthese.append("(");
            recParentheses(parentheses, n, left + 1, right, parenthese);
            parenthese.deleteCharAt(parenthese.length() - 1);
        }
        
        if (right < left) {
            parenthese.append(")");
            recParentheses(parentheses, n, left, right + 1, parenthese);
            parenthese.deleteCharAt(parenthese.length() - 1);
        }
        
        return;
    }
    
    
    public static void main(String[] args) {
        Question9_6 question9_6 = new Question9_6();
        LinkedList<String> parentheses = question9_6.parentheses(4);
        for (String parenthese : parentheses) {
            System.out.println(parenthese);
        }
    }
}