Home Generate Parentheses
Post
Cancel

LeetCode #22: Generate Parentheses (C/C++).

medium

source: https://leetcode.com/problems/generate-parentheses/
C/C++ Solution to LeetCode problem 22. Generate Parentheses.

Problem


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

Examples


Example 1:

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

Example 2:

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

Constraints


  • 1 <= n <= 8

Solution


  • We will use Dynamic Programing.
  • We know that we need n open parentheses '()' and n close parentheses ')'.
  • There cannot be (at any time) less '(' than ')' in our current solution.
  • The method will count how many '(' and ')' are still availabe to add to the current solution.
  • Once there are 0 '(' than ')' left, we add that solution to the final result.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {

private:
  vector<string> result;
  void generate(string s, int o, int c) {
    if (o == 0 && c == 0)
      result.push_back(s);
    
    if (o)
      generate(s + "(", o - 1, c);
    if (o<c)
      generate(s + ")", o, c - 1);
  }

public:
  vector<string> generateParenthesis(int n) {
    generate("", n, n);
    return result;
  }
};
This post is licensed under CC BY 4.0 by the author.

Merge Two Sorted Lists

Swap Nodes in Pairs