22. Generate Parentheses.md

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){
	        //对于某一个点，如果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);
	    }
	}

二刷

一开始就想到了用递归来做，但是没想到好的思路，还是参考了一刷时候的方法。

定义左右括号的数量(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);
            }
        }
    }
}

Fourth time

• Method 1: recursion

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

C++ Version

• Method 1: traceback with restriction

   class Solution {
   private:
   	void dfs(int left, int right, string s){
   		if(left == 0 && right == 0) res_.emplace_back(s);
   		if(left > 0)    dfs(left - 1, right, s + "(");
   		if(right > left) dfs(left, right - 1, s + ")");
   	}
   	vector<string> res_;
   public:
   	vector<string> generateParenthesis(int n) {
   		if(!n) return res_;
   		dfs(n, n, "");
   		return res_;
   	}
   };