Leetcode 90 Subsets II

Given an integer array nums that may contain duplicates, 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,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

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

• Soruda bize sayılardan oluşan bir liste veriliyor bu listede aynı sayılar olabilir. Ve bu listenin benzersiz alt kümelerini bulmamız isteniyor.Örneğin elimizde [1,2,2] şeklinde bir liste var.Bu listenin normalde [1,2] , [1,2] şeklinde aynı alt kümeyi birden fazla oluşturma ihtimali var.Bu durumda bunlardan sadece birini sonuç listemize ekleyeceğiz.
• Bu sorunun çözümü için subset probleminde olduğu gibi backtracking yöntemi ile aynı fonksiyonu tekrar tekrar çağırabiliriz.
• Her çağırdığımızda oluşan combination listesini sonuç listemizde olup olmadığını kontrol ederiz.Yok ise ekleriz var ise geçeriz.
• Burada dikkat etmemiz gereken dfs fonksiyonu çağrılmadan önce kombinasyon kümesine eklenen elemanın çağrıldıktan sonra kombinasyondan çıkarılması işlemidir.Bu sayede kombinasyon kümesi sadece ilk verilen listenin alt kümelerinden oluşur.
• Çıkarma işlemi yapılarak oluşan çağrılar.
• dfs fonksiyonu çağrılıp ilk for döngüsü başladığı zaman 0,1,2 indexleri için dfs tekrar çağrılır.
• İndex 0 çağrısında 0,1,2 indexteki 1,2,2 sayıları eklenir ve çıkarılır.

ekle  indeks 0 [1]
ekle  indeks 1 [1, 2] burada indeks 1 deki 2 ekleniyor
ekle  indeks 2 [1, 2, 2]
çikar indeks 2 [1, 2]
çikar indeks 1 [1]
ekle  indeks 1 [1, 2] burada indeks 2 deki 2 ekleniyor
çikar indeks 1 [1]
çikar indeks 0 []

• İndex 1 çağrısında 1. ve 2. indeksteki 2’ler eklenir ve çıkarılır.

ekle  indeks 0 [2] burada indeks 1 deki 2 ekleniyor
ekle  indeks 2 [2, 2] burada indeks 2 deki 2 ekleniyor
çikar indeks 2 [2]
çikar indeks 0 []

• İndex 2 çağrısı sadece 2. indexteki 2 eklenir ve çıkarılır.

ekle  indeks 0 [2]
çikar indeks 0 []

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        def dfs(results, combination, start, nums):
            if combination not in results:
                results.append(list(combination))
        
            for i in range(start, len(nums)):
                combination.append(nums[i])            
                dfs(results, combination, i + 1, nums)            
                combination.pop()
                
        results = []
        combination = []
        nums = sorted(nums)

        dfs(results,combination , 0, nums)
        
        return results