« Back
in Leetcode Java Backtracking String read.

Leetcode 22 Generate Parentheses.

Problem 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:

"((()))", "(()())", "(())()", "()(())", "()()()"


Many people say it is a easy problem, but I do not think so.

As the idea is easy, but writing it out is another thing.

If n=6, then you have 6 "(" and 6 ")", then you have to make them line up in order. So you have 12 blank, and the number of ")" should less than or equal to "(".

That is it. Simple, right?

But the problem is how to express when you used "(" and ")". So the solution is recursion.

public class Solution {
public ArrayList generateParenthesis(int n) {
    ArrayList solutions = new ArrayList();
    recursion(n, new String(), solutions);
    return solutions;
}

private void recursion(int n, String str, ArrayList sol) {
    if(str.length() == 2 * n)
        sol.add(str);
    else {
        int left = 0;
        int right = 0;
        for(int i = 0; i < str.length(); ++i) {
            if(str.charAt(i) == '(')
                left++;
            if(str.charAt(i) == ')')
                right++;
        }
        if(left == right)
            recursion(n, str + "(", sol);
        else if(right < left) {
            if(left < n)
                recursion(n, str + "(", sol);
            recursion(n, str + ")", sol);
        }
    }
}
}
comments powered by Disqus