import java.util.ArrayList;

import java.util.Stack;

public class Num9_6 {

    //判断是否是合法的括号字符串

    /*

     * 遇到左括号入栈，遇到右括号则栈顶元素出栈（在栈不为空的情况下，栈为空则返回false），遇到其他字符则返回false

     * 判断栈是否为空，为空则合法，不为空则不合法

     */

    public boolean chkParenthesis(String A, int n) {

        // write code here

        if (n < 2)

            return false;

        Stack<Character> sc = new Stack<Character>();

        for (int i = 0; i < A.length(); i++) {

            if (A.charAt(i) == '(')

                sc.push('(');

            else if (A.charAt(i) == ')') {

                if (sc.isEmpty())

                    return false;

                sc.pop();

            } else

                return false;

        }

        if (sc.isEmpty())

            return true;

        return false;

    }

    //求n对括号的有效组合

    /*

     * 遵循括号的构成语法，如果左括号还有剩余则使用左括号，如果剩余的右括号比左括号多，则可以使用右括号

     * 左括号与右括号都用尽了，则新生成了一个括号组合

     */

    ArrayList<String> ans = new ArrayList<String>();

    public ArrayList<String> getParenthesis(int n) {

        String s = "";

        getAll(n, n, s);

        return ans;

    }

    public void getAll(int left, int right, String s) {

        if (left == 0 && right == 0) {

            ans.add(s);

        }

        if (left > 0) {

            getAll(left - 1, right, s + "(");

        }

        if (right > 0 && right > left) {

            getAll(left, right - 1, s + ")");

        }

    }

}