22.括号生成.md

22. 括号生成

url

题目

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
输入：n = 1
输出：["()"]

方法

code

js

let generateParenthesis = n => {
    let dfs = (ans, cnt1, cnt2, n) => {
        if (cnt1 > n || cnt2 > n)
            return;
        if (cnt1 === n && cnt2 === n)
            ret.push(ans);
        if (cnt1 >= cnt2){
            dfs(ans + "(", cnt1 + 1, cnt2, n);
            dfs(ans + ")", cnt1, cnt2 + 1, n);
        }
    };
    let ret = []
    dfs("", 0, 0, n);
    return ret;
};

go

func generateParenthesis(n int) []string {
	var res []string
	var dfs func(ans string, cnt1 int, cnt2 int, n int)
	dfs = func (ans string, cnt1 int, cnt2 int, n int) {
		if cnt1 > n || cnt2 > n {
			return
		}
		if cnt1 == n && cnt2 == n {
			res = append(res, ans)
		}
		if cnt1 >= cnt2 {
			//ans1 := ans
			dfs(ans + "(", cnt1 + 1, cnt2, n)
			dfs(ans + ")", cnt1, cnt2 + 1, n)
		}
	}
	dfs("", 0, 0, n)
	return res
}

java

class Solution {
    List<String> ret = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        dfs("", 0, 0, n);
        return ret;
    }

    public void dfs(String ans, int cnt1, int cnt2, int n){
        if (cnt1 > n || cnt2 > n)
            return;
        if (cnt1 == n && cnt2 == n)
            ret.add(ans);
        if (cnt1 >= cnt2){
            String ans1 = new String(ans);
            dfs(ans + "(", cnt1 + 1, cnt2, n);
            dfs(ans + ")", cnt1, cnt2 + 1, n);
        }
    }
}