Leetcode 78 Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Input: nums = [0]
Output: [[],[0]]

• Soruda bize sayılardan oluşan bir liste veriliyor ve bu listenin alt kümelerini bulmamız isteniyor.
• Bir kümenin alt kümeleri sayısı o kümenin eleman sayısı üzeri 2 (n^2) dir.
• Bu soruda dfs adında oluşturacağımız fonksiyonu tekrar tekrar çağırarak dallanmış olarak tüm alt kümelere ulaşabiliriz.
• Yapacağımız işlem elimizdeki elemanı ekleyerek ve eklemeyerek dfs fonksiyonunu çağırmak.
• Örneğin [1,2] elemanlı kümenin 4 altkümesi oluşabilir.
• İlk dfs fonksiyonu çağırdığımızda 1. eleamanın olduğu ve olmadığı 2 alt küme oluşur [] ,[1].
• İkinci dfs fonksiyonu çağırmada ilk olara [] alt kümesine 2 yi ekleriz [2] ve 2yi eklemeyiz [] şimdi de [1] alt kümesine 2yi ekleriz [1,2] eklemeyiz [1] bu şekilde dallanmış bir yapı oluşur ve sonuç olarak [] ,[1],[2],[1,2] alt kümeleri oluşur.

    def subsets(self, nums: List[int]) -> List[List[int]]:
        res= [] #sonuç
        subset = [] #alt kümelerin oluştuğu değişken her seferinde değişecek.
        
        def dfs(i):
            if i >= len(nums): #eğer indeksin sonuna geldiysem elindeki alt kümeyi sonuca kopyala ve dön
                res.append(subset.copy())
                return
            #alt kümeye yeni elemanı ekle dfs çağır     
            subset.append(nums[i])
            dfs(i+1)
            #alt kümeye eklediğin yeni elemanı çıkar dfs çağır  
            subset.pop()
            dfs(i+1)
        dfs(0)
        return res