class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<String>();
        backtrack(ans, new StringBuilder(), 0, 0, n);
        return ans;
    }
    public void backtrack(List<String> ans, StringBuilder cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            ans.add(cur.toString());
            return;
        }
        if (open < max) {
            cur.append('(');
            backtrack(ans, cur, open + 1, close, max);
            cur.deleteCharAt(cur.length() - 1);
        }
        if (close < open) {
            cur.append(')');
            backtrack(ans, cur, open, close + 1, max);
            cur.deleteCharAt(cur.length() - 1);
        }
    }
}

時間復(fù)雜度：o(4^n / n^(1/2))

空間復(fù)雜度：o(n)

方法一：深度優(yōu)先遍歷（go）

具體方法分析已在上文中表述

根據(jù)題目條件生成一顆樹，并對這顆樹生枝葉的條件按照題目進行限制。

需要左右括號都大于0個時才可以進行生成樹的操作（等于0的特殊情況）

生成樹之后生出左節(jié)點的條件：左括號的剩余數(shù)量大于0

生成樹之后生成右節(jié)點條件：左括號的剩余數(shù)量小于右括號的剩余數(shù)量

當(dāng)左右括號都為0時，為成功出口，此時進行結(jié)算，保存結(jié)果。

	var ans []string
	var backtrack func([]byte, int, int)
	backtrack = func(bytes []byte, left int, right int) {
		if len(bytes) == 2*n {
			ans = append(ans, string(bytes))
			return
		}
		if left < n {
			bytes = append(bytes,'(')
			backtrack(bytes, left+1, right)
			bytes = bytes[:len(bytes)-1]
		}
		if right < left{
			bytes = append(bytes, ')')
			backtrack(bytes, left, right + 1)
			bytes = bytes[:len(bytes)-1]
		}
	}
	var container []byte
	backtrack(container, 0, 0)
	return ans

時間復(fù)雜度：o(4^n / n^(1/2))

空間復(fù)雜度：o(n)

以上就是Go java 算法之括號生成示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go java 算法括號生成的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: