题解 | #括号生成#

这一题刚拿到手可能没啥思路解决，不知道采用什么数学方法，但是你要看到所有可能的括号组合。所有二字，摆明是搜索题，可以dfs或者bfs，这里采用dfs完成。

dfs搜索需要考虑遍历所有情况，还有就是初始和停止的条件，我们知道dfs是回溯的，如果字符串频繁创建删除效率很低，所以利用回溯回来过程将字符串还原(StringBuilder)这样可以大大提升效率。而具体需要这样思考：

n对括号，说明有n个(和n个)，可用两个数字标记两个个数。 (个数不能小于)的个数，否则不满足有效括号。 如果(用完，那么只能添加)，如果(未用完且不满足小于)个数，那么当前既可添加(也可添加)。 注意作用域，参数等问题 具体实现代码为：

import java.util.*;
import java.util.ArrayList;
import java.util.List;

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
     ArrayList<String>list;
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        list=new ArrayList<String>();
		StringBuilder sBuilder=new StringBuilder();
		dfs(sBuilder,0,0,n);
		return list;
    }
    
    private void dfs(StringBuilder sBuilder, int i, int j,int n) {
		if(j==n) {list.add(sBuilder.toString());return;}
		if(i<j)return;
		if(i<n)
		{
			sBuilder.append('(');
			dfs(sBuilder, i+1, j, n);
			sBuilder.deleteCharAt(i+j);
		}
		if(i>j)
		{
			sBuilder.append(')');
			dfs(sBuilder, i, j+1, n);
			sBuilder.deleteCharAt(i+j);
		}
		
	}
}