Leetcode 22 Generate Parentheses

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

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

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

• Soruda bize n sayısı veriliyor.Ve bu n sayısı kadar parantes kullanarak kaç farklı düzgün “()” parantez kombinasyonu yapabiliriz diye soruyor.
• Algoritma çıkarmak için temel kurallar koymak istersek eğer 3 temel kural bulabiliriz.
• Açık parantezi sadece açık parantez sayısı < n ise ekle
• Kapalı parantezi sadece kapalı parantez sayısı < açık parantez sayısı ise ekle
• Eğer açık parantez sayısı == kapalı parantez sayısı == n ise oluşan kombinasyonu sonuç listesine ekle.
• Oluşturacağımız backtrack fonksiyonunda bu kontrolleri yaparsak rekürsif olarak fonksiyonu çağırarak kombinasyonları bulabiliriz.

    def generateParenthesis(self, n: int) -> List[str]:
        
        parent = []
        res = []
        
        def backtrack(openN,closedN):
            if openN == closedN == n:
                res.append("".join(parent))
                return
            if openN < n:
                parent.append("(")
                backtrack(openN + 1,closedN)
                parent.pop()
            
            if closedN <openN:
                parent.append(")")
                backtrack(openN,closedN + 1)
                parent.pop()
                
        backtrack(0,0)
        return res