# Print all combinations of balanced parentheses

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

### Example:

• Input: `n = 2`
• Output: `["(())", "()()"]`

### Approach: Backtracking

To solve this problem, we use backtracking to explore all possible combinations of parentheses. The idea is to generate strings by adding `'('` and `')'` recursively, while ensuring that at any point:

• We do not have more closing parentheses `')'` than opening `'('`.
• We do not exceed `n` pairs of parentheses.

### Generate Parentheses Code in JavaScript:

``````function generateParentheses(n) {
const result = [];

function backtrack(openCount, closeCount, current) {
if (current.length === n * 2) {
result.push(current);
return;
}

if (openCount < n) {
backtrack(openCount + 1, closeCount, current + '(');
}

if (closeCount < openCount) {
backtrack(openCount, closeCount + 1, current + ')');
}
}

backtrack(0, 0, '');
return result;
}

// Example Usage
console.log(generateParentheses(2)); // Output: ["(())", "()()"]
``````

### Explanation of the Code

1. Backtracking Function: The `backtrack` function is called recursively to build the combinations.
2. Parameters:
• `openCount`: Number of `'('` used so far.
• `closeCount`: Number of `')'` used so far.
• `current`: Current string being built.
3. Base Case: If the length of `current` equals `n * 2` (since each pair has two characters), we have a valid combination.
4. Recursive Calls:
• Add `'('` if possible: If `openCount` is less than `n`, we can add another `'('`.
• Add `')'` if valid: If `closeCount` is less than `openCount`, we can add a `')'` to maintain balance.

### Recursive State Tree (n = 2)

The diagram below represents the recursive state tree for generating parentheses with `n = 2`.

`#mermaid-svg-NitFpQm5p0GTQH3u{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#000000;}#mermaid-svg-NitFpQm5p0GTQH3u .error-icon{fill:#552222;}#mermaid-svg-NitFpQm5p0GTQH3u .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-NitFpQm5p0GTQH3u .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-NitFpQm5p0GTQH3u .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-NitFpQm5p0GTQH3u .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-NitFpQm5p0GTQH3u .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-NitFpQm5p0GTQH3u .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-NitFpQm5p0GTQH3u .marker{fill:#666;stroke:#666;}#mermaid-svg-NitFpQm5p0GTQH3u .marker.cross{stroke:#666;}#mermaid-svg-NitFpQm5p0GTQH3u svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-NitFpQm5p0GTQH3u .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#000000;}#mermaid-svg-NitFpQm5p0GTQH3u .cluster-label text{fill:#333;}#mermaid-svg-NitFpQm5p0GTQH3u .cluster-label span{color:#333;}#mermaid-svg-NitFpQm5p0GTQH3u .label text,#mermaid-svg-NitFpQm5p0GTQH3u span{fill:#000000;color:#000000;}#mermaid-svg-NitFpQm5p0GTQH3u .node rect,#mermaid-svg-NitFpQm5p0GTQH3u .node circle,#mermaid-svg-NitFpQm5p0GTQH3u .node ellipse,#mermaid-svg-NitFpQm5p0GTQH3u .node polygon,#mermaid-svg-NitFpQm5p0GTQH3u .node path{fill:#eee;stroke:#999;stroke-width:1px;}#mermaid-svg-NitFpQm5p0GTQH3u .node .label{text-align:center;}#mermaid-svg-NitFpQm5p0GTQH3u .node.clickable{cursor:pointer;}#mermaid-svg-NitFpQm5p0GTQH3u .arrowheadPath{fill:#333333;}#mermaid-svg-NitFpQm5p0GTQH3u .edgePath .path{stroke:#666;stroke-width:1.5px;}#mermaid-svg-NitFpQm5p0GTQH3u .flowchart-link{stroke:#666;fill:none;}#mermaid-svg-NitFpQm5p0GTQH3u .edgeLabel{background-color:white;text-align:center;}#mermaid-svg-NitFpQm5p0GTQH3u .edgeLabel rect{opacity:0.5;background-color:white;fill:white;}#mermaid-svg-NitFpQm5p0GTQH3u .cluster rect{fill:hsl(210,66.6666666667%,95%);stroke:#26a;stroke-width:1px;}#mermaid-svg-NitFpQm5p0GTQH3u .cluster text{fill:#333;}#mermaid-svg-NitFpQm5p0GTQH3u .cluster span{color:#333;}#mermaid-svg-NitFpQm5p0GTQH3u div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(-160,0%,93.3333333333%);border:1px solid #26a;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-NitFpQm5p0GTQH3u:root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;}#mermaid-svg-NitFpQm5p0GTQH3u flowchart{fill:apa;}Start: '' (open=0, close=0)Add '(': '(' (open=1, close=0)Add '(': '((' (open=2, close=0)Add ')': '(()' (open=2, close=1)Add ')': '(())' (open=2, close=2)Add ')': '()' (open=1, close=1)Add '(': '()(' (open=2, close=1)Add ')': '()()' (open=2, close=2)`

### Explanation of the Diagram:

• Root Node `A` (“Start: ‘’”): Start with an empty string, with `open` and `close` counts at `0`.
• Node `B1` (“Add ‘(’: ‘(’ (open=1, close=0)”): Add an opening parenthesis `'('` to the string, incrementing `open` to `1`.
• Node `C1` (“Add ‘(’: ‘((’ (open=2, close=0)”): Add another `'('`, incrementing `open` to `2`.
• Node `D1` (“Add ‘)’: ‘(()’ (open=2, close=1)”): Now we must add a closing parenthesis `')'` since `open` has reached `n`.
• Node `E1` (“Add ‘)’: ‘(())’ (open=2, close=2)”): Add another `')'`, reaching `n` pairs, and we have a valid combination `'(())'`.
• Node `C2` (“Add ‘)’: ‘()’ (open=1, close=1)”): Backtrack to a valid state and add `')'`.
• Node `D2` (“Add ‘(’: ‘()(’ (open=2, close=1)”): Add another `'('`, creating `open=2`.
• Node `E2` (“Add ‘)’: ‘()()’ (open=2, close=2)”): Add the last `')'` to form another valid combination `"()()"`.

### Key Points to Remember:

1. Recursive Exploration: Explore all possible valid combinations by adding `'('` and `')'`.
2. Backtracking: Use backtracking to undo the last action and explore other possibilities when necessary.
3. Valid Parentheses Check: Maintain the condition that at no point can the count of `')'` exceed the count of `'('`.

.

No Comment