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: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

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; } };