程式小試身手

一個"("必定有另一個")" 所以n=1時2*1, n=2時2*2,n=3時2*3, 總結就是2*n個符號

不可能有")"先開始,所以驗證時 "( "balance 只會為正或為 0,<0 直接 return false

n=1, [()]

n=2, [(()),()()]

n=3, [((())),(()()),(())(),()(()),()()()]

----------------------------------

public List<String> generateParenthesis(int n) {
           List<String> combinations = new ArrayList();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }
      public void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (valid(current))
            {
                result.add(new String(current));
                
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }

    public boolean valid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') balance++;
            else balance--;
            if (balance < 0) return false;
        }
        return (balance == 0);
    }