Skip to main content

Leetcode 22: Generate Parentheses

 

1. Problem Statement (Simple Explanation):


You are given an integer n, the number of pairs of parentheses.

You must generate all possible combinations of well-formed (valid) parentheses using exactly n pairs.

A string of parentheses is well-formed if:

  • Every opening '(' has a corresponding closing ')'.

  • At any point while reading from left to right, the number of ')' never exceeds '('.


2. Examples:


Example 1:

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

These are all valid combinations using exactly 3 pairs.


Example 2:

Input: n = 1

Output: ["()"]


Constraints:

  • 1 <= n <= 8


3. Approach – Backtracking (DFS with Constraints):


This is a classic backtracking problem.


Intuition:


We want to build strings of length 2 * n using '(' and ')', but only keep the valid ones.

Instead of generating all 22n possibilities and filtering, we build only valid strings by enforcing rules during construction.

We keep track of:

  • open = number of '(' used so far

  • close = number of ')' used so far

Rules to keep the string valid at all times:

  1. We can add '(' if open < n.

  2. We can add ')' if close < open (we can’t close more than we’ve opened).

When the string length reaches 2 * n, we have a complete valid combination.


Algorithm (Step-by-Step):


  1. Initialize an empty result list.

  2. Define a recursive function backtrack(path, open, close):

    • path: current string being built.

    • open: number of '(' used.

    • close: number of ')' used.

  3. Base case:

    • if len(path) == 2 * n:

      • Add path to result; return.

  4. Recursive cases:

    • if open < n: we can add '(':

      • backtrack(path + "(", open + 1, close)

    • if close < open: we can add ')':

      • backtrack(path + ")", open, close + 1)

  5. Start recursion with: backtrack("", 0, 0).

  6. Return the result list.


Pseudo-code:



Complexity:


Asymptotically,

  • Time: O(Cn) (we generate each valid string once).

  • Space:

    • Recursion depth: O(n).

    • Output size: O(n*Cn) characters total.

For n <= 8, this is very manageable.


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:


Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more