Leetcode 46 Permutations
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Input: nums = [0,1]
Output: [[0,1],[1,0]]
Input: nums = [1]
Output: [[1]]
- Soruda bize sayılardan oluşan bir liste veriliyor.Bu listedeki sayıların permutasyonlarını bulmamız isteniyor.
- Burada 90. sorudaki gibi bir yardımcı fonksiyon yazıp bu fonksiyonu tekrar tekrar çağırarak sonuçlara ulaşabiliriz.
- Helper fonksiyonu 5 parametre alıyor.results-> sonuç listemiz, nums->sorunun başında bize verilen sayı listesi, combination->listedeki sayılarla oluşturduğumuz kombinasyonlar, start-başlangıç indeksi, visited->daha önce kullandığımız sayıları tekrar kullanmamamız için sayıları tuttuğumuz liste.
- Helper fonksiyonu içindeki ilk kontrolümüz eğer kombinasyon uzunluğu liste uzunluğuna ulaştı ise fonksiyonu return et.Bu şekilde elimizdeki sayılardan oluşan bir permütasyon bulduk.
- Daha sonra elimizdeki listedeki sayıları 0. indeksten liste sonuna kadar tarayıp.İndeksteki sayıyı önce visited listesine sonrada kombinasyon listesine ekleriz ve helper fonksiyonunu tekrar çağırırız.
- Helper fonksiyonu çağrıldıktan sonra ise indeksteki sayıyı hem visited listesinden hem de kombinasyondan çıkarırız.
- Aşağıdaki örnekte ilk permutasyonun nasıl bulunduğuna bakalım.
- ekle 0 1 {1} [1] -> yapılan işlem-indeks-indeksteki sayı-ziyaret edilmiş sayılar-elimizdeki kombinasyon
ekle 0 1 {1} [1] İlk olarak 0. indeksteki 1 rakamı hem visited hem kombinasyona ekleniyor helper çağrılıyor.
devam 0 1 {1} [1] Visited kontrol et ve 1 eklendiği için devam et ekleme yapma helper çağırma.
ekle 1 2 {1, 2} [1, 2] 1. indeksteki 2 rakamı hem visited hem kombinasyona ekleniyor helper çağrılıyor.
devam 0 1 {1, 2} [1, 2] Visited kontrol et ve 1 eklendiği için devam et ekleme yapma helper çağırma.
devam 1 2 {1, 2} [1, 2] Visited kontrol et ve 2 eklendiği için devam et ekleme yapma helper çağırma.
ekle 2 3 {1, 2, 3} [1, 2, 3] 2. indeksteki 3 rakamı hem visited hem kombi. ekleniyor helper çağrılıyor.
buldu {1, 2, 3} [1, 2, 3] kombinasyon uzunluğu ve nums uzunluğu eşit bir permütasyon bulduk.
çıkar 2 3 {1, 2} [1, 2] 2. indeksteki 3 rakamı hem visited hem kombi. çıkar.
çıkar 1 2 {1} [1] 1. indeksteki 2 rakamı hem visited hem kombi. çıkar.
- Burada ilk helper çağrısındaki 1 visited eklendikten sonra çağrılan helper işleminde ki for döngüsünde bulunan indeks 1 artıyor.1 visited eklenmişti daha önce 2 eklendi ve çıkarıldı.Şimdi de 3 eklenecek ve çıkarılacak.
ekle 2 3 {1, 3} [1, 3]
devam 0 1 {1, 3} [1, 3]
ekle 1 2 {1, 2, 3} [1, 3, 2]
buldu {1, 2, 3} [1, 3, 2]
çıkar 1 2 {1, 3} [1, 3]
devam 2 3 {1, 3} [1, 3]
çıkar 2 3 {1} [1]
çıkar 0 1 set() []
ekle 1 2 {2} [2]
ekle 0 1 {1, 2} [2, 1]
devam 0 1 {1, 2} [2, 1]
devam 1 2 {1, 2} [2, 1]
ekle 2 3 {3, 1, 2} [2, 1, 3]
buldu {3, 1, 2} [2, 1, 3]
çıkar 2 3 {1, 2} [2, 1]
çıkar 0 1 {2} [2]
devam 1 2 {2} [2]
ekle 2 3 {3, 2} [2, 3]
ekle 0 1 {1, 2, 3} [2, 3, 1]
buldu {1, 2, 3} [2, 3, 1]
çıkar 0 1 {2, 3} [2, 3]
devam 1 2 {2, 3} [2, 3]
devam 2 3 {2, 3} [2, 3]
çıkar 2 3 {2} [2]
çıkar 1 2 set() []
ekle 2 3 {3} [3]
ekle 0 1 {1, 3} [3, 1]
devam 0 1 {1, 3} [3, 1]
ekle 1 2 {1, 3, 2} [3, 1, 2]
buldu {1, 3, 2} [3, 1, 2]
çıkar 1 2 {1, 3} [3, 1]
devam 2 3 {1, 3} [3, 1]
çıkar 0 1 {3} [3]
ekle 1 2 {3, 2} [3, 2]
ekle 0 1 {1, 3, 2} [3, 2, 1]
buldu {1, 3, 2} [3, 2, 1]
çıkar 0 1 {3, 2} [3, 2]
devam 1 2 {3, 2} [3, 2]
devam 2 3 {3, 2} [3, 2]
çıkar 1 2 {3} [3]
devam 2 3 {3} [3]
çıkar 2 3 set() []
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
def permute(self, nums: List[int]) -> List[List[int]]:
def helper(results, nums, combination, start, visited):
if len(combination) == len(nums):
results.append(list(combination))
return
for i in range(len(nums)):
if nums[i] in visited:
continue
visited.add(nums[i])
combination.append(nums[i])
helper(results, nums, combination, i + 1, visited)
combination.pop()
visited.remove(nums[i])
results = []
visited = set()
helper(results, nums, [], 0, visited)
return results