[Leetcode] Generate Parentheses

22. Generate Parentheses

Given npairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

1 <= n <= 8

How to understand?

given n is integer which is the number of the valid parenthesis pair.

so we are going to find 2n length of strings which has valid parenthesis pair.

the valid parenthesis will be opened and closed at right location.

How to approach?

Brute force

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def isValid(p_string):
            left_count = 0
            for p in p_string:
                if p == "(":
                    left_count += 1
                else:
                    left_count -= 1

                if left_count < 0:
                    return False

            return left_count == 0

        answer = []
        queue = collections.deque([""])
        while queue:
            cur_string = queue.popleft()

            if len(cur_string) == 2 * n:
                if isValid(cur_string):
                    answer.append(cur_string)
                continue
            queue.append(cur_string + ")")
            queue.append(cur_string + "(")

        return answer

1. this way will look for all the parenthesis pair length of 2n.
2. and validate if it can be answer or not.
3. create the answer array and the deque which has empty string.
4. while loop will check items in deque.
5. first, check out the left most item in deque as cur_string.
6. and if the cur_string's length 2*n then send it to validation step.
7. if it's valid then append it to the answer array.
8. other than that, add ")" and add "(" to the current string. and then append those 2 in the deque.
9. while deque exist, keep pop left it out and append it.
10. in the validation function, it will count the left_count based on the opening bracket's number in the string. and if it's same as 0 return true or not false. if it is less than 0 then it is not valid so return false.
11. lastly return the valid answer array.

summary

This way is checking all the possible parenthesis pairs. BFS technique is used.

Backtracking

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        answer = []

        def backtracking(cur_string, left_count, right_count):
            if len(cur_string) == 2 * n:
                answer.append("".join(cur_string))
                return
            if left_count < n:
                cur_string.append("(")
                backtracking(cur_string, left_count + 1, right_count)
                cur_string.pop()
            if right_count < left_count:
                cur_string.append(")")
                backtracking(cur_string, left_count, right_count + 1)
                cur_string.pop()

        backtracking([], 0, 0)
        return answer

1. first create answer array.
2. and backtracking function will take empty array and left_count, right_count
3. the first parameter is a string of "(" and ")" , first it will check the length of the string if it is 2*n then append it to the answer array by joining.
4. if condtion to check if the left_count is less than n, then cur_string will have "("
5. and recursively called backtracking function with left_count+1 value.
6. and when it reached 2*n length of current_string then returned, it will pop the last element out.
7. when right_count is less than left_count it means the opening bracket is more than closing bracket. so append the ")" and call the backtracking function recursively with right_count + 1 value.
8. when it's returned after hit the 2*n length, pop the last element out to choose another possible path.
9. lastly return the answer array.

summary

this use DFS, and not wasting time to check invalid parenthesis pair. since it only find the valid parenthesis pair.