22. Generate Parentheses

Question:

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:

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

Thinking:

• Method1: Recursive

    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList<>();
            bp(result, "", 0, 0, n);
            return result;
        }
        private void bp(List<String> result, String par, int left, int right, int n){
            //����ijһ���㣬����left��right��������n��˵�����������ӵģ��ͣ����Ѿ��������ˡ�
            if(left == n && right == n){
                result.add(par);
                return;
            }
            //���ӣ������������ĸ���С��n
            if(left < n) bp(result, par+"(", left+1, right, n);
            //���ӣ������������ĸ���С�ڣ�
            if(right < left) bp(result, par+")", left, right+1, n);
        }
    }
  

• Method2:Recursive

    class Solution {
        public List<String> generateParenthesis(int n) {
            List<String> result = new ArrayList<String>();
            backtrace(result, "", n, n);
            return result;
        }
        private void backtrace(List<String> result, String par, int left, int right){
            if(left == 0 && right == 0){
                result.add(par);
                return;
            }
            if(left > 0)    backtrace(result, par+"(", left - 1, right);
            if(right > 0 && left < right)   backtrace(result, par+")", left, right - 1);
        }
    }
  

��ˢ

һ��ʼ���뵽���õݹ�����������û�뵽�õ�˼·�����Dzο���һˢʱ���ķ�����

�����������ŵ�����(left, right)������left����0��������һ��(������right����0����right����left��������һ��)��

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        if(n == 0) return result;
        backtrace(result, "", n, n);
        return result;
    }
    private void backtrace(List<String> result, String s, int left, int right){
        if(left == 0 && right == 0){
            result.add(s);
            return;
        }
        if(left > 0) backtrace(result, s + "(", left - 1, right);
        if(right > 0 && right > left) backtrace(result, s + ")", left, right - 1);
    }
}

Third time

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