Generate Parentheses


  • 0

    Click here to see the full article post


  • 0
    R

    In approach 2 for java str.length() should be cur.length().


  • 0
    A

    slight optimization : for all cases where c = (n-1)/2 , Aren't we calling the function twice ?


  • 0

    @ankush6 We could memoize our function, yes.


  • 0
    W

    There should be a section in this article for backtracking solution (#2) w/ memoization


  • 1
        def generateParenthesisDFS(self, n):
            def generate(s, left, right, ans):
                if len(s) == 2*n:
                    ans.append(s)
                if left < n:
                    generate(s+'(', left+1, right, ans)
                if left > right:
                    generate(s+')', left, right+1, ans)
            left, right, ans = 0, 0, []
            generate('', left, right, ans)
            return ans
    
        def generateParenthesisBFS(self, n):
            def valid(s, n):
                bal, left = 0, 0
                for c in s:
                    if c == '(': 
                        bal += 1
                        left += 1
                    else:
                        bal -= 1
                    if bal < 0:
                        return False
                return bal >= 0 and left <= n
    
            ans = []
            q = Queue.Queue()
            q.put('(')
            while not q.empty():
                s = q.get()
                if len(s) == 2*n:
                    ans.append(s)
                    continue
                for i in ['(', ')']:
                    if valid(s+i, n):
                        q.put(s+i)
            return ans
    

  • 0
    S

    @awice I don't get why the space complexity for the brute force approach is O(2^2n * n).
    In my understanding the approach generates an anonymous character array of 2n length by generateAll(new char[2 * n], 0, combinations), and pass this anonymous array for the rest of the recursion. And when the recursion reach the end of the anonymous array, it returns and overwrite '(' with ')'.
    If my understanding is right, then the Space complexity is O(2n).


  • 0
    This post is deleted!

  • 0
    H

    @wierzba
    Here is a python code with memorization in iterative flavor:

    class Solution:
        def generateParenthesis(self, n):
            """
            :type n: int
            :rtype: List[str]
            """
    
            if n == 0:
                return []
    
            if n == 1:
                return ['()']
    
            memory = dict()
            memory[0] = set()
            memory[1] = set(['()'])
    
            # n > 1
    
            for x in range(1, n + 1):
                result = memory.get(x, set())
                for y in range(1, x):
                    print('x ', x, ' y ', y)
                    for subresult_head in memory[y]:
                        for subresult_tail in memory[x - y]:
                            concatanation = subresult_head + subresult_tail
                            result.add(concatanation)
    
                for subresult in memory[x-1]:
                    inbetween = '(' + subresult + ')'
                    result.add(inbetween)
    
                memory[x] = result
    
            return result

  • 0
    K

    I know this problem will use backtracking, but I can't write the code. How do you come up with the code? How should I practice, do anyone tell me


  • 0

    @kunlaotou To be able to come up with a good solution to a backtracking problem, a very good grasp on recursion is required.
    I like to think of it this way,
    Recursion is nothing but all the possible situations that arise in a problem.
    Backtracking is very similar to recursion, but you should know which case(s) will not be a part of the solution.

    Bonus,
    Having a good knowledge of recursion will also help you come up with DP solutions.
    Let me know your thoughts and how you plan to proceed.


  • 1
    K

    @baby_groot Thanks for your reply! "Recursion is nothing but all the possible situations that arise in a problem" help me a lot!
    I've practiced recursion with Tower of Hanoi and others.
    I think recursion is a kind of thinking to solve the problem from simple to complex. However, it's hard to me to code completely correct.
    I always write the variable values on paper to help me understand the recursion step by step, I should pratice more code.
    Do you have better advice? Thank you!


  • 0
    F

    @haoyu6 It can be simplified:

    class Solution(object):
        self.dict = {0: ['']}
        def generateParenthesis(self, n):
            if n < 1: return []
            for i in range(1, n + 1):
                iCombos = []
                for numPairsInLeft in range(1, i + 1):
                    for left in self.dict[numPairsInLeft - 1]:
                        for right in self.dict[i - numPairsInLeft]:
                            iCombos.append('({}){}'.format(left, right))
                self.dict[i] = iCombos
            return self.dict[n]

  • 0
    N

    There is no variable 'str' defined in approach 2


  • 0
    P

    BAD test cases. The order should not matter.
    For example, the following should be the same:
    ["(())","()()"]
    ["()()","(())"]


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.