Leetcode 22 Generate Parentheses

Soru

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

Örnek 1

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

Örnek 2

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

Çözüm

• n çift parantez kullanarak oluşturulabilecek tüm geçerli parantez kombinasyonlarını üretmenizi isteyen bir problem. Burada geçerli bir kombinasyon, her açılan parantezin bir kapanış parantezi ile eşleşmesi ve herhangi bir zamanda açık parantez sayısının kapanan parantez sayısını geçmemesi gerektiğini ifade eder.
• Girdi: Bir tam sayı n, kaç çift parantez kullanılacağını belirtir.
• Çıktı: Tüm geçerli parantez kombinasyonlarını içeren bir string listesi.
• Bu problem genellikle derinlik öncelikli arama (DFS) veya geriye dönük arama (backtracking) yöntemiyle çözülür. Rekürsif bir fonksiyon, şu anda oluşturulmuş parantez dizisine dayanarak, adım adım tüm geçerli kombinasyonları oluşturur.
• Çalışma Mekanizması:
• Rekürsif Backtracking Fonksiyonu: backtrack adında bir iç fonksiyon tanımlanır. Bu fonksiyon, şu ana kadar oluşturulan string s ve açık (left) ile kapalı (right) parantez sayılarını parametre olarak alır.
• Son Durum Kontrolü: Eğer s’nin uzunluğu 2*n’ye eşitse, bu string sonuç listesine eklenir.
• Açık Parantez Ekleme: Eğer açık parantez sayısı n’den azsa, bir açık parantez eklenir ve backtrack tekrar çağrılır.
• Kapanış Parantez Ekleme: Eğer kapalı parantez sayısı açık parantez sayısından azsa, bir kapalı parantez eklenir ve backtrack tekrar çağrılır.
• Sonuç: Tüm rekürsif çağrılar tamamlandığında, result listesi döndürülür.

Code

    class Solution:
    def generateParenthesis(self, n):
        def backtrack(s='', left=0, right=0):
            if len(s) == 2 * n:
                # String uzunluğu maksimuma ulaştıysa sonuç listesine ekle
                result.append(s)
                return
            if left < n:
                # Daha fazla açık parantez eklenebilir
                backtrack(s + '(', left + 1, right)
            if right < left:
                # Geçerli diziye daha fazla kapanış parantezi eklenmesi mümkün
                backtrack(s + ')', left, right + 1)

        result = []
        backtrack()
        return result

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(4^n / √n), Catalan sayısına dayalı bir büyüme oranı gösterir, bu nedenle oldukça hızlı büyür ancak pratikte genellikle yönetilebilir.
• Space complexity (Alan Karmaşıklığı) : O(n), rekürsif çağrı yığını için kullanılan alan, maksimum rekürsif derinlikle orantılıdır.