-2

I want to generate all possible permutations of a set of parentheses of a certain length N.

Example:

if N = 1
Output: ['()']

if N = 3
Output: ['()(())', '(())()', '(()())', '((()))', '()()()']
Fijaja Mulla
  • 17
  • 5
  • 2
    https://www.geeksforgeeks.org/print-all-combinations-of-balanced-parentheses/ – JRose Sep 03 '22 at 05:04
  • 1
    Does this answer your question? [How to print all possible balanced parentheses for an expression?](https://stackoverflow.com/questions/6447289/how-to-print-all-possible-balanced-parentheses-for-an-expression) – Joe Sep 03 '22 at 05:33

2 Answers2

2

Credit: https://prepinsta.com/python-program/generate-all-combinations-of-balanced-parentheses/

def generateParenthesis(n, Open, close, s, ans):

    if Open == n and close == n:
        ans.append(s)
        return

    if Open < n:
        generateParenthesis(n, Open + 1, close, s + "(", ans)

    if close < Open:
        generateParenthesis(n, Open, close + 1, s + ")", ans)


n = 3
ans = []
generateParenthesis(n, 0, 0, "", ans)
for s in ans:
    print(s)
Yaser Sakkaf
  • 164
  • 2
  • 10
1

As a fresher I came up with this solution where I create all the possible combinations using the function generate_permutations and then create a new list with only valid parentheses:

def generate_permutations(current, perms, prefix=''):
    if len(current) == 0:
        perms.add(prefix)

    for i in range(len(current)):
        new_prefix = prefix + current[i]
        new_current = current[:i] + current[i+1:]
        generate_permutations(new_current, perms, new_prefix)
    return perms


def refine(l):
    os = list()
    cs = list()
    res = list()
    for each in l:
        flag = True
        for e in each:
            if e == '(':
                os.append(e)
            elif e == ')':
                cs.append(e)
                if os and os[-1] == '(':
                    os = os[:-1]
                    cs = cs[:-1]
                else:
                    flag = False
                    break
        if flag:
            res.append(each)
    return res

    
N = 3
string = "()" * N
answer_list = generate_permutations(string, set())
refined = refine(answer_list)
print(refined)
Fijaja Mulla
  • 17
  • 5