leetcode-22-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:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

DFS 回溯的味道

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        Stack<String> stack = new Stack<String>();
        Stack<int[]> gen = new Stack<int[]>();
        stack.push("");
        gen.push(new int[]{n, 0});
        while(!stack.isEmpty())
        {
            String s = stack.pop();
            int open = gen.peek()[0];
            int close = gen.pop()[1];
            
            if(open == 0 && close == 0)
                result.add(s);
            if(open > 0)
            {
                stack.push(s + "(");
                gen.push(new int[]{open - 1, close + 1});
            }
            if(close > 0)
            {
                stack.push(s + ")");
                gen.push(new int[]{open,close - 1});
            }
        }
        return result;
    }
}