CODEWITHSUNDEEP
python
Kevin
Kevin

Reputation: 391

Trying to solve the n-parenthesis problem - but failing

I am trying to implement a solution to the 'n-parenthesis problem'

def gen_paren_pairs(n): 
   
   
    def gen_pairs(left_count, right_count, build_str, build_list=[]):
        
        print(f'left count is:{left_count}, right count is:{right_count}, build string is:{build_str}')
        
        if left_count == 0 and right_count == 0:
            build_list.append(build_str)
            print(build_list)
            return build_list
            
        if left_count > 0:
            build_str += "("
            gen_pairs(left_count - 1, right_count, build_str, build_list)
            
        
        if left_count < right_count:
            build_str += ")"
            #print(f'left count is:{left_count}, right count is:{right_count}, build string is:{build_str}')
            gen_pairs(left_count, right_count - 1, build_str, build_list)
        
     
    in_str = ""
    gen_pairs(n,n,in_str)
 


gen_paren_pairs(2)

It almost works but isn't quite there. The code is supposed to generate a list of correctly nested brackets whose count matches the input 'n'

Here is the final contents of a list. Note that the last string starts with an unwanted left bracket.

['(())', '(()()']

Please advise.

Upvotes: 0

Views: 68

Answers (1)

Scott Hunter
Scott Hunter

Reputation: 49838

Here's a less convoluted approach:

memory = {0:[""]}
def gp(n):
    if n not in memory:
        local_mem = []
        for a in range(n):
            part1s = list(gp(a))
            for p2 in gp(n-1-a):
                for p1 in part1s:
                    pat = "("+p1+")"+p2
                    local_mem.append(pat)
        memory[n] = local_mem
    return memory[n]

The idea is to take one pair of parentheses, go over all the ways to divide the remaining N-1 pairs between going inside that pair and going after it, find the set of patterns for each of those sizes, and make all of the combinations.

To eliminate redundant computation, we save the values returned for each input n, so if asked for the same n again, we can just look it up.

Upvotes: 1

Related Questions