Skip to content

22. Generate Parentheses

DifficultyMedium

Description

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

 

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

 

Constraints:

  • 1 <= n <= 8

Solutions

Solution 1: DFS + Pruning

Thinking

The first idea is to enumerate every string of length \(2n\) and keep the valid ones. \(n \le 8\) gives \(2^{16}\) candidates, so it would pass, but most prefixes are already illegal.

The bottleneck is generate-then-check: once a prefix has more ) than (, or either count exceeds \(n\), no suffix can save it.

A valid prefix only needs the two counts \(l\) and \(r\): keep \(l \ge r\) and neither above \(n\). When \(l=r=n\), record the string.

DFS therefore tries appending ( or ) and prunes on those three inequalities. The search tree is much smaller than full enumeration; extra space is just the current string, \(O(n)\).

The range of \(n\) in the problem is \([1, 8]\), so we can directly solve this problem through "brute force search + pruning".

We design a function \(dfs(l, r, t)\), where \(l\) and \(r\) represent the number of left and right brackets respectively, and \(t\) represents the current bracket sequence. Then we can get the following recursive structure:

  • If \(l \gt n\) or \(r \gt n\) or \(l \lt r\), then the current bracket combination \(t\) is invalid, return directly;
  • If \(l = n\) and \(r = n\), then the current bracket combination \(t\) is valid, add it to the answer array ans, and return directly;
  • We can choose to add a left bracket, and recursively execute dfs(l + 1, r, t + "(");
  • We can also choose to add a right bracket, and recursively execute dfs(l, r + 1, t + ")").

The time complexity is \(O(2^{n\times 2} \times n)\), and the space complexity is \(O(n)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def dfs(l: int, r: int, t: str):
            if l > n or r > n or l < r:
                return
            if l == n and r == n:
                ans.append(t)
                return
            dfs(l + 1, r, t + "(")
            dfs(l, r + 1, t + ")")

        ans = []
        dfs(0, 0, "")
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    private List<String> ans = new ArrayList<>();
    private int n;

    public List<String> generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0, "");
        return ans;
    }

    private void dfs(int l, int r, String t) {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.add(t);
            return;
        }
        dfs(l + 1, r, t + "(");
        dfs(l, r + 1, t + ")");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        auto dfs = [&](this auto&& dfs, int l, int r, string t) -> void {
            if (l > n || r > n || l < r) {
                return;
            }
            if (l == n && r == n) {
                ans.push_back(t);
                return;
            }
            dfs(l + 1, r, t + "(");
            dfs(l, r + 1, t + ")");
        };
        dfs(0, 0, "");
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
func generateParenthesis(n int) (ans []string) {
    var dfs func(int, int, string)
    dfs = func(l, r int, t string) {
        if l > n || r > n || l < r {
            return
        }
        if l == n && r == n {
            ans = append(ans, t)
            return
        }
        dfs(l+1, r, t+"(")
        dfs(l, r+1, t+")")
    }
    dfs(0, 0, "")
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
function generateParenthesis(n: number): string[] {
    const dfs = (l: number, r: number, t: string) => {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.push(t);
            return;
        }
        dfs(l + 1, r, t + '(');
        dfs(l, r + 1, t + ')');
    };
    const ans: string[] = [];
    dfs(0, 0, '');
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn generate_parenthesis(n: i32) -> Vec<String> {
        let mut ans = Vec::new();

        fn dfs(ans: &mut Vec<String>, l: i32, r: i32, t: String, n: i32) {
            if l > n || r > n || l < r {
                return;
            }
            if l == n && r == n {
                ans.push(t);
                return;
            }
            dfs(ans, l + 1, r, format!("{}(", t), n);
            dfs(ans, l, r + 1, format!("{})", t), n);
        }

        dfs(&mut ans, 0, 0, String::new(), n);
        ans
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    const dfs = (l, r, t) => {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.push(t);
            return;
        }
        dfs(l + 1, r, t + '(');
        dfs(l, r + 1, t + ')');
    };
    const ans = [];
    dfs(0, 0, '');
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    private List<string> ans = new List<string>();
    private int n;

    public List<string> GenerateParenthesis(int n) {
        this.n = n;
        Dfs(0, 0, "");
        return ans;
    }

    private void Dfs(int l, int r, string t) {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.Add(t);
            return;
        }
        Dfs(l + 1, r, t + "(");
        Dfs(l, r + 1, t + ")");
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private $ans = [];
    private $n = 0;

    /**
     * @param Integer $n
     * @return String[]
     */
    function generateParenthesis($n) {
        $this->n = $n;
        $this->ans = [];
        $this->dfs(0, 0, '');
        return $this->ans;
    }

    private function dfs($l, $r, $t) {
        if ($l > $this->n || $r > $this->n || $l < $r) {
            return;
        }
        if ($l == $this->n && $r == $this->n) {
            $this->ans[] = $t;
            return;
        }
        $this->dfs($l + 1, $r, $t . '(');
        $this->dfs($l, $r + 1, $t . ')');
    }
}

Comments