題目描述

image

解題思路

我們可以將問題改寫成：
現(xiàn)在有2n個位置，每個位置可以放 ( 或者 )，組成的所有括號組合中，哪些是合法的？
解決這個問題只需要分2步：

1. 暴力枚舉所有可能的情況，共有2的2n次方
2. 在做選擇之前，進(jìn)行“剪枝”

1、暴力枚舉

只需要直接套用回溯算法的框架即可：

• 當(dāng)path的長度為2n時，滿足結(jié)束條件，將path加入res中
• 基于選擇列表【"(", ")"】，做選擇
• 遞歸調(diào)用
• 撤銷選擇

const dfs = function(path) {
    if(path.length === 2*n){
    res.push(path.join(""))
    }

    path.push('(')
    dfs(path)
    path.pop()

    path.push(')')
    dfs(path)
    path.pop()
}

2、“剪枝”

基于當(dāng)前的路徑，如何判斷當(dāng)前的括號組合是否合法？
不難發(fā)現(xiàn)：如果當(dāng)前的路徑中，左括號數(shù)量小于右括號的數(shù)量，那么這一定是不合法的括號組合

如何判斷當(dāng)前路徑已經(jīng)結(jié)束？
很簡單，只要看路徑的長度是否為2n即可

代碼實(shí)現(xiàn)(JavaScript)

在核心函數(shù)dfs中，我們可以用2個變量left和right，記錄已經(jīng)使用的左右括號數(shù)量
在做選擇之前：

• 對當(dāng)前路徑的合法性進(jìn)行判斷
• 判斷當(dāng)前路徑是否滿足結(jié)束條件

var generateParenthesis = function(n) {
    const res = new Array()

    const dfs = function(left,right,path) {
        if(left>n || right>n) {
            return
        }
        if(left < right) {
            return
        }
        if(path.length === 2*n){
            res.push(path.join(""))
            return
        }
        
        path.push('(')
        dfs(left+1, right, path)
        path.pop()

        path.push(')')
        dfs(left, right+1,path)
        path.pop()
    }

    dfs(0,0,[])
    return res
};