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