Generate Valid Parentheses

Given a number n, your task is to generate all combinations of well-formed parentheses. This is a classic problem that tests understanding of recursion and backtracking algorithms, crucial for many combinatorial and structural problems in computer science.

Problem Description

You are given an integer n representing the number of pairs of parentheses. Your goal is to write a function that generates all possible and valid combinations of parentheses. A string of parentheses is considered "well-formed" if:

1. The total number of opening parentheses ( equals the total number of closing parentheses ).
2. At any point while scanning the string from left to right, the number of opening parentheses encountered must be greater than or equal to the number of closing parentheses.

You need to return a list or array containing all these valid combinations.

Examples

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Explanation: For n=3, we have 3 pairs of parentheses. The output lists all 5 unique combinations that are well-formed.

Example 2:

Input: n = 1
Output: ["()"]
Explanation: For n=1, the only valid combination is a single pair of parentheses.

Example 3:

Input: n = 0
Output: [""]
Explanation: When n is 0, there are no parentheses to form. The only valid combination is an empty string.

Constraints

• 1 <= n <= 8
• The input n will be an integer.
• The solution should aim for an efficient time complexity, typically related to the Catalan numbers.

Notes

• This problem can be effectively solved using a recursive backtracking approach.
• Consider keeping track of the number of open and closed parentheses available at each step of the generation process.
• Think about the conditions that determine whether placing an opening or closing parenthesis is valid at any given step.
• The order of the strings in the output list does not matter.