Generate Parentheses: BFS, DFS

这个题目虽然简单，但是有两种做法。一种recursive DFS，一种queue的iterative BFS

    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        gen(result, 0, 0, n, "");
        return result;
    }
    private void gen(List<String> result, int left, int right, int n, String tmp) {
        if (left == right && left == n)
            result.add(tmp);
        else if (left >= right && left <= n ){
            gen(result, left, right+1, n, tmp + ")");
            gen(result, left+1, right, n, tmp +"(");
        }
    }

    class Elem {
        int left;
        int right;
        String str;
        Elem(int l, int r, String s) {
            left = l;
            right = r;
            str = s;
        }
    }
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        Queue<Elem> queue = new LinkedList<Elem>();
        queue.add(new Elem(0,0,""));
        while (!queue.isEmpty()) {
            Elem elem = queue.poll();
            if (elem.left == elem.right && elem.left == n) {
                result.add(elem.str);
            }
            if (elem.left >= elem.right && elem.left < n) {
                queue.add(new Elem(elem.left+1, elem.right, elem.str + "("));
            }
            if (elem.left >= elem.right && elem.right < n) {
                queue.add(new Elem(elem.left, elem.right+1, elem.str + ")"));
            }
        }
        return result;
    }