Bir labirentte çıkışı aradığını düşün. Her kavşakta yollardan birini seçiyorsun; seçtiğin yol çıkmaza varırsa son kavşağa dönüyor ve henüz denemediğin bir yola sapıyorsun. Elinde harita yok ama bir yöntemin var: sistemli biçimde dene, olmuyorsa geri dön, sıradaki seçeneği dene. Geri izleme (backtracking), bu gündelik stratejinin algoritmaya dönüşmüş hâlidir.
Birçok problem aslında "olası tüm yapılandırmalar arasından koşulları sağlayanları bul" cümlesine indirgenebilir: bir kümenin bütün alt kümeleri, bir listenin bütün sıralanışları, toplamı belirli bir hedefe eşit sayı grupları, birbirini tehdit etmeyen vezir yerleşimleri, bir sudoku bulmacasının çözümü. Bu problemlerin ortak noktası, çözümün küçük kararların art arda verilmesiyle kurulmasıdır. Geri izleme bu kararları örtük bir ağaç üzerinde gezer: her adımda bir seçim yapar, o seçimle devam edip neler olduğunu keşfeder, sonra seçimi geri alıp bir sonraki seçeneğe geçer. Kısmi bir çözümün artık hiçbir geçerli çözüme tamamlanamayacağını fark ettiği anda da o dalı keser. Bu budama (pruning), geri izlemeyi kör bir kaba kuvvetten ayıran şeydir.
Bu dersin sonunda seç, keşfet, geri al şablonunu Go'da rahatça yazabilecek; alt küme, permütasyon ve kombinasyon üretimini tekrarlı girdiler dahil hatasız yapabilecek; N-Vezir, sudoku ve ızgarada kelime arama gibi kısıt problemlerini çözebileceksin. Budamanın etkisini çağrı sayılarıyla ölçecek, bu algoritmaların karmaşıklığını hesaplayacak ve Go dilimlerinin (slice) geri izlemede yol açtığı sinsi bir hatayı tanıyacaksın. Özyinelemede kendini henüz rahat hissetmiyorsan önce Özyineleme dersine göz atmanı öneririm; burada çağrı yığınının nasıl çalıştığını bildiğini varsayacağız.
Karar ağacı: geri izlemenin zihinsel modeli
Her geri izleme algoritmasının arkasında örtük bir karar ağacı vardır:
- Kök, henüz hiçbir kararın verilmediği boş kısmi çözümdür.
- Her kenar bir seçimdir: "1'i al", "bu satırdaki veziri 3. sütuna koy" gibi.
- Her düğüm, kökten o düğüme kadar verilen kararların oluşturduğu kısmi çözümdür.
- Yapraklar ya tam bir aday çözümdür ya da ilerlemenin anlamsız olduğu bir çıkmazdır.
Bu ağaç bellekte hiçbir zaman bütünüyle oluşturulmaz. Özyineleme onu derinlik öncelikli olarak gezer ve herhangi bir anda yalnızca kökten bulunduğun düğüme kadar olan yol, yani o yol boyunca verilmiş kararlar bellekte durur. Ağaçta milyonlarca düğüm olsa bile ek bellek ihtiyacı ağacın derinliğiyle sınırlı kalır.
Somut bir örnekle başlayalım: [1, 2, 3] kümesinin tüm alt kümelerini üretmek istiyoruz. Her eleman için tek bir soru soruyoruz: "Bu eleman alt kümeye girsin mi?" Üç eleman, üç karar düzeyi demektir:
[]
├── 1 al ─── [1]
│ ├── 2 al ─── [1 2]
│ │ ├── 3 al ─── [1 2 3]
│ │ └── 3 alma ─ [1 2]
│ └── 2 alma ─ [1]
│ ├── 3 al ─── [1 3]
│ └── 3 alma ─ [1]
└── 1 alma ─ []
├── 2 al ─── [2]
│ ├── 3 al ─── [2 3]
│ └── 3 alma ─ [2]
└── 2 alma ─ []
├── 3 al ─── [3]
└── 3 alma ─ []Ağacın derinliği 3 ve her iç düğümün iki çocuğu var; dolayısıyla 2³ = 8 yaprak oluşuyor ve her yaprak tam olarak bir alt kümeye karşılık geliyor. Geri izleme bu ağacı yukarıdan aşağıya, soldan sağa gezer: önce en soldaki dalın sonuna (1 al → 2 al → 3 al) kadar iner, [1 2 3] sonucunu kaydeder, sonra bir üst düğüme dönüp "3 alma" seçeneğini dener ve bu böyle sürer.
Seç, keşfet, geri al şablonu
Karar ağacını gezen kodun iskeleti hemen her problemde aynıdır. Aşağıdaki parça çalıştırılabilir bir program değil; bu derste her çözümde yeniden karşına çıkacak kalıbın kendisi:
func backtrack(state *State, results *[]Solution) {
if state.IsComplete() {
*results = append(*results, state.Snapshot()) // kopyasını kaydet
return
}
for _, choice := range state.Candidates() {
if !state.IsValid(choice) {
continue // budama: bu seçim hiçbir çözüme götürmez
}
state.Apply(choice) // 1. seç
backtrack(state, results) // 2. keşfet
state.Undo(choice) // 3. geri al
}
}Parçaları tek tek inceleyelim:
- Tamamlanma kontrolü (temel durum): Kısmi çözüm tam bir çözüm hâline geldiyse kaydedilir ve geri dönülür.
- Adaylar: Bulunduğun düğümde yapılabilecek seçimler. Alt kümelerde "al / alma", permütasyonlarda "henüz kullanılmamış elemanlar", N-Vezir'de "bu satırın sütunları".
- Geçerlilik kontrolü: Kısıtı ihlal eden bir seçim, alt ağacına hiç inilmeden elenir. Budama tam olarak burada gerçekleşir.
- Seç: Ortak durum yerinde değiştirilir: dilime eleman eklenir, bir işaret
trueyapılır, tahtaya vezir konur. - Keşfet: Güncel durumla bir alt düzeye inilir.
- Geri al: Özyinelemeli çağrı döndükten sonra durum, seçimden önceki hâline getirilir.
Algoritmanın doğruluğu tek bir değişmeze (invariant) dayanır: backtrack çağrısı döndüğünde durum, çağrı yapılmadan önceki durumla birebir aynıdır. Bu değişmez korunduğu sürece döngünün her turu aynı başlangıç durumundan yola çıkar ve kardeş dallar birbirinin izlerini görmez. Geri al adımı unutulursa bir dalda yapılan değişiklik bir sonraki dala sızar ve sonuçlar sessizce bozulur.
Peki neden her düğümde durumun yeni bir kopyasını oluşturmuyoruz? Oluşturabilirdik; o zaman geri almaya da gerek kalmazdı. Ancak her kopyalama O(n) zaman ve bellek harcar ve bu bedeli ağaçtaki her düğüm için ödersin. Tek bir ortak durumu değiştirip geri almak ise ek bellek ihtiyacını ağacın derinliğiyle, yani çoğu problemde O(n) ile sınırlar. Kopyalamayı yalnızca bir sonucu kaydederken yaparız.
Alt kümeler (subsets)
Problem: Elemanları birbirinden farklı bir nums tamsayı dilimi veriliyor. Tüm alt kümeleri (kuvvet kümesini) döndür. Örneğin [1, 2, 3] için sonuç 8 alt kümedir: [], [1], [2], [3], [1 2], [1 3], [2 3], [1 2 3]. Sonuçların sırası önemli değildir.
Bu problemi iki farklı karar ağacıyla çözebiliriz. İkisini de bilmek önemli, çünkü dersin geri kalanındaki problemlerin hepsi bu iki kalıptan birinin üzerine kurulur.
Yaklaşım 1: Dahil et ya da etme
Yukarıda çizdiğimiz ağacı doğrudan koda döküyoruz. backtrack(i) çağrısı "nums[i] hakkında karar ver" anlamına geliyor. i == len(nums) olduğunda bütün kararlar verilmiştir ve path bir alt kümedir.
package main
import (
"fmt"
"slices"
)
func subsets(nums []int) [][]int {
var result [][]int
var path []int
var backtrack func(i int)
backtrack = func(i int) {
if i == len(nums) {
result = append(result, slices.Clone(path))
return
}
// 1. dal: nums[i] alt kümeye girsin.
path = append(path, nums[i]) // seç
backtrack(i + 1) // keşfet
path = path[:len(path)-1] // geri al
// 2. dal: nums[i] alt kümeye girmesin.
backtrack(i + 1)
}
backtrack(0)
return result
}
func main() {
for _, s := range subsets([]int{1, 2, 3}) {
fmt.Println(s)
}
}[1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []
Birkaç ayrıntıya dikkat et. backtrack bir closure (kapanış) olarak tanımlandı; böylece nums, path ve result değişkenlerini her çağrıda parametre olarak taşımak zorunda kalmıyoruz. Closure'ın kendini çağırabilmesi için önce var backtrack func(i int) ile bildirilip sonra atandığına dikkat et. "Dahil etme" dalında durumu hiç değiştirmediğimiz için orada geri alınacak bir şey de yok.
Algoritmanın ilk adımlarını izleyelim:
path hiçbir zaman len(nums) elemandan uzun olmuyor ve çağrı yığınında aynı anda en fazla len(nums) + 1 çerçeve bulunuyor. Sonuçları kaydederken neden slices.Clone(path) kullandığımızı birazdan göreceğiz.
Yaklaşım 2: Başlangıç indeksiyle döngü
İkinci bakış açısında her düğüm doğrudan bir alt kümedir. Bir düğümden, o ana kadar seçilen son elemandan sonra gelen elemanlardan birini ekleyerek çocuk düğümlere geçeriz:
[]
├── [1]
│ ├── [1 2]
│ │ └── [1 2 3]
│ └── [1 3]
├── [2]
│ └── [2 3]
└── [3]Bu ağaçta 8 düğüm var ve her biri farklı bir alt küme. "Yalnızca sonraki elemanlar" kuralı, aynı kümenin farklı bir sırayla yeniden üretilmesini engeller: [2] düğümünden 1'e geri dönülemediği için [2 1] hiç oluşmaz.
package main
import (
"fmt"
"slices"
)
func subsets(nums []int) [][]int {
var result [][]int
var path []int
var backtrack func(start int)
backtrack = func(start int) {
result = append(result, slices.Clone(path)) // her düğüm bir alt küme
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
return result
}
func main() {
fmt.Println(subsets([]int{1, 2, 3}))
}[[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]]
Her çağrı girer girmez mevcut path değerini kaydeder, sonra start indeksinden itibaren her elemanı sırayla dener. Özyinelemeli çağrıya start + 1 değil i + 1 geçirildiğine dikkat et: az önce seçilen elemanın hemen sonrasından devam etmek istiyoruz. Bu ayrıntı, kombinasyon problemlerinin de bel kemiğidir.
Alt küme sayısı 2ⁿ'dir ve her birini kopyalamak O(n) sürer; toplam O(n · 2ⁿ). Ek alan, path ve çağrı yığını için O(n)'dir; sonuç listesinin kendisi (O(n · 2ⁿ)) bu hesaba katılmaz. Çıktının boyutu zaten bu kadar büyük olduğundan, tüm alt kümeleri listeleyen hiçbir algoritma bundan hızlı olamaz. Aynı problemi bit maskeleriyle özyinelemesiz çözmek de mümkündür; bunu Bit Manipülasyonu dersinde göreceksin.
Go'ya özgü tuzak: path dilimini kopyalamadan eklemek
Yukarıdaki kodlarda slices.Clone(path) yerine doğrudan path eklemek çok cazip görünür. Deneyelim:
package main
import "fmt"
func main() {
nums := []int{1, 2, 3}
var result [][]int
var path []int
var backtrack func(start int)
backtrack = func(start int) {
result = append(result, path) // HATA: yalnızca dilim başlığı kopyalanır
for i := start; i < len(nums); i++ {
path = append(path, nums[i])
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(0)
fmt.Println(result)
}[[] [1] [1 2] [3 3 3] [3 3] [3] [3 3] [3]]
Sekiz sonuç var ama yalnızca ilk üçü doğru; geri kalanların hepsi 3'lerle dolu. Nedeni, bir Go diliminin elemanların kendisi değil, alttaki diziyi gösteren bir başlık (işaretçi, uzunluk, kapasite) olmasıdır. append(result, path) yalnızca bu başlığın bir kopyasını saklar; elemanlar paylaşılmaya devam eder. (Dilim başlığını hatırlamak istersen: Diziler ve Dilimler.)
Adım adım ne olduğuna bakalım:
pathbaştanil.append1'i eklerken kapasite yetmediği için 1 kapasiteli yeni bir dizi (A) ayırır. Kaydedilen[1]başlığı A'yı gösterir.- 2 eklenirken kapasite yine yetmez; 2 kapasiteli yeni dizi B ayrılır. Kaydedilen
[1 2]başlığı B'yi gösterir. - 3 eklenirken 4 kapasiteli dizi C ayrılır. Bundan sonra kapasite hiç aşılmadığı için
pathhep C üzerinde büyüyüp küçülür. path = path[:len(path)-1]yalnızca uzunluğu azaltır; sonrakiappendaynı hücrelerin üzerine yazar. Arama bittiğinde C'nin ilk üç hücresi3, 3, 3olur ve C'yi gösteren beş başlığın hepsi bu hücreleri okur.
result[0] ── nil → []
result[1] ── A: [ 1 ] → [1]
result[2] ── B: [ 1 | 2 ] → [1 2]
result[3] ─┐
result[4] ─┤
result[5] ─┼─► C: [ 3 | 3 | 3 | _ ] → uzunluklarına göre [3 3 3], [3 3], [3] ...
result[6] ─┤
result[7] ─┘İlk üç sonucun doğru çıkması tamamen tesadüftür: append o anda yeni bir dizi ayırdığı için eski başlıklar artık kimsenin yazmadığı dizileri gösteriyordu. path dilimini make([]int, 0, len(nums)) ile önceden ayırsaydın hiçbir sonuç doğru çıkmazdı. Çözüm, kaydetme anında elemanları kopyalamaktır:
- result = append(result, path) // HATA: yalnızca dilim başlığı kopyalanır
+ result = append(result, slices.Clone(path))Permütasyonlar
Problem: Elemanları birbirinden farklı nums diliminin tüm sıralanışlarını (permütasyonlarını) döndür. [1, 2, 3] için 3! = 6 sonuç vardır.
Bu kez karar "bu eleman girsin mi?" değil, "sıradaki konuma hangi eleman gelsin?" sorusudur. İlk konum için 3, ikinci konum için kalan 2, sonuncu için 1 seçenek vardır; ağacın 3 · 2 · 1 = 6 yaprağı olur:
[]
┌───────────────┼───────────────┐
[1] [2] [3]
┌───┴───┐ ┌───┴───┐ ┌───┴───┐
[1 2] [1 3] [2 1] [2 3] [3 1] [3 2]
│ │ │ │ │ │
[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]used dilimi ile
Hangi elemanların yolda olduğunu used adlı bir boolean dilimde tutarız. Her konumda, henüz kullanılmamış elemanları sırayla deneriz:
package main
import (
"fmt"
"slices"
)
func permute(nums []int) [][]int {
var result [][]int
path := make([]int, 0, len(nums))
used := make([]bool, len(nums)) // used[i]: nums[i] şu an yolda mı?
var backtrack func()
backtrack = func() {
if len(path) == len(nums) {
result = append(result, slices.Clone(path))
return
}
for i, x := range nums {
if used[i] {
continue
}
used[i] = true // seç
path = append(path, x)
backtrack() // keşfet
path = path[:len(path)-1]
used[i] = false // geri al
}
}
backtrack()
return result
}
func main() {
for _, p := range permute([]int{1, 2, 3}) {
fmt.Println(p)
}
}[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 1 2] [3 2 1]
Seç adımında iki şeyi birden değiştiriyoruz (used[i] ve path), bu yüzden geri al adımında ikisini de ters sırayla eski hâline getiriyoruz. Girdi sıralıysa sonuçlar sözlük sırasında (lexicographic) çıkar, çünkü her konumda adaylar küçükten büyüğe denenir.
n! yaprağın her birinde O(n) maliyetli bir kopya yapılır. k derinliğindeki düğüm sayısı n!/(n−k)! olduğundan iç düğümlerin toplamı da en fazla e · n! kadardır ve her düğümdeki döngü O(n) sürer; toplam O(n · n!). Ek alan path, used ve çağrı yığını için O(n)'dir.
Yer değiştirme (swap) yaklaşımı
Ayrı path ve used dilimleri kullanmadan, permütasyonu doğrudan nums üzerinde kurmak da mümkün. Fikir şu: nums[:k] bölümü sabitlenmiş önek, nums[k:] bölümü ise henüz yerleştirilmemiş elemanlar. k. konuma nums[k:] içindeki her elemanı sırayla yer değiştirerek getir, k + 1 için devam et, dönünce yeniden yer değiştirerek geri al.
package main
import (
"fmt"
"slices"
)
func permute(nums []int) [][]int {
var result [][]int
var backtrack func(k int)
backtrack = func(k int) {
if k == len(nums) {
result = append(result, slices.Clone(nums))
return
}
for i := k; i < len(nums); i++ {
nums[k], nums[i] = nums[i], nums[k] // seç: nums[i] k. konuma gelsin
backtrack(k + 1) // keşfet
nums[k], nums[i] = nums[i], nums[k] // geri al
}
}
backtrack(0)
return result
}
func main() {
fmt.Println(permute([]int{1, 2, 3}))
}[[1 2 3] [1 3 2] [2 1 3] [2 3 1] [3 2 1] [3 1 2]]
Çıktının sonuna dikkat: [3 2 1], [3 1 2]'den önce geliyor; yani sonuçlar sözlük sırasında değil. k = 0 iken 1 ile 3 yer değiştirdiğinde dizi [3 2 1] olur ve alt ağaç bu düzenden başlar. Bu yöntem daha az ek bellek kullanır, ama sıra önemliyse used yaklaşımını tercih et. nums yerinde değiştiği için k == len(nums) anında kopya almak burada da zorunlu.
Tekrarlı elemanlarla permütasyonlar: sırala ve atla
Girdide tekrar eden değerler varsa, örneğin [1, 1, 2], yukarıdaki kod 6 sonuç üretir ama bunların yalnızca 3'ü birbirinden farklıdır: [1 1 2], [1 2 1], [2 1 1]. Sonuçları bir kümeye atıp tekrarları sonradan ayıklamak çalışır, ama gereksiz dalları yine de gezer. Daha iyisi, tekrar üretecek dalları hiç açmamaktır.
İki eşit 1'i ayırt etmek için birine 1a, diğerine 1b diyelim. [1a 1b 2] ile [1b 1a 2] aynı sonuçtur. Bu tekrarı önlemek için eşit değerlerin her zaman soldan sağa sırayla kullanılmasını şart koşarız: 1b ancak 1a zaten yoldaysa seçilebilir. Önce diziyi sıralayıp eşit değerleri yan yana getiririz, sonra şu koşulu sağlayan adayı atlarız:
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
continue
}!used[i-1] ne anlama geliyor? Döngü aynı konum için 1a'yı zaten denemiş, bütün alt ağacını gezmiş ve geri almış demektir (bu yüzden artık yolda değil). Şimdi 1b'yi aynı konuma koymak, az önce gezilen alt ağacın aynısını yeniden üretmekten başka bir işe yaramaz.
package main
import (
"fmt"
"slices"
)
func permuteUnique(nums []int) [][]int {
nums = slices.Sorted(slices.Values(nums)) // sıralı kopya: eşitler yan yana
var result [][]int
path := make([]int, 0, len(nums))
used := make([]bool, len(nums))
var backtrack func()
backtrack = func() {
if len(path) == len(nums) {
result = append(result, slices.Clone(path))
return
}
for i, x := range nums {
if used[i] {
continue
}
// Aynı değerin önceki kopyası bu konumda denenip geri alındıysa atla.
if i > 0 && x == nums[i-1] && !used[i-1] {
continue
}
used[i] = true
path = append(path, x)
backtrack()
path = path[:len(path)-1]
used[i] = false
}
}
backtrack()
return result
}
func main() {
for _, p := range permuteUnique([]int{1, 2, 1}) {
fmt.Println(p)
}
fmt.Println("[2 1 2 1] için", len(permuteUnique([]int{2, 1, 2, 1})), "farklı permütasyon")
}[1 1 2] [1 2 1] [2 1 1] [2 1 2 1] için 6 farklı permütasyon
Sonuç sayısı, tekrarlı permütasyon formülüyle uyumlu: iki 1 ve iki 2 içeren dört eleman için 4! / (2! · 2!) = 6.
Kombinasyonlar ve hedef toplam
C(n, k): n sayıdan k tanesini seçmek
Problem: 1'den n'ye kadar olan sayılardan k tanesini seçmenin tüm yollarını döndür. n = 4, k = 2 için 6 kombinasyon vardır: [1 2], [1 3], [1 4], [2 3], [2 4], [3 4].
Bu, alt kümelerdeki başlangıç indeksi kalıbının neredeyse aynısı; tek fark yalnızca uzunluğu k olan düğümleri kaydedip orada durmamız. Ayrıca basit ama etkili bir budama ekleyebiliriz: yolda len(path) sayı varsa, daha need = k - len(path) sayı seçmemiz gerekir. Sıradaki sayı n - need + 1 değerinden büyükse ondan sonra yeterince sayı kalmaz. Örneğin n = 4, k = 2 ve yol boşken ilk sayı en fazla 3 olabilir; 4 ile başlayan bir kombinasyonun ikinci elemanı olamaz.
package main
import (
"fmt"
"slices"
)
func combine(n, k int) [][]int {
var result [][]int
path := make([]int, 0, k)
var backtrack func(start int)
backtrack = func(start int) {
if len(path) == k {
result = append(result, slices.Clone(path))
return
}
need := k - len(path)
for i := start; i <= n-need+1; i++ { // budama: yeterli sayı kalsın
path = append(path, i)
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(1)
return result
}
func main() {
fmt.Println(combine(4, 2))
fmt.Println("C(5, 3) =", len(combine(5, 3)))
}[[1 2] [1 3] [1 4] [2 3] [2 4] [3 4]] C(5, 3) = 10
Sonuç sayısı C(n, k) = n! / (k! · (n−k)!) ve her sonucun kopyalanması O(k) sürer. Budama sayesinde gezilen her düğüm en az bir geçerli kombinasyona tamamlanabilir; boşa açılan dal kalmaz ve düğüm sayısı sonuç sayısının en fazla k + 1 katı olur.
Kombinasyon toplamı: adaylar tekrar kullanılabilir
Problem: Birbirinden farklı pozitif tamsayılardan oluşan candidates ve bir target veriliyor. Toplamı target olan tüm kombinasyonları bul; her aday sınırsız sayıda kullanılabilir. [2, 3, 6, 7] ve hedef 7 için cevap [2 2 3] ve [7]'dir.
Başlangıç indeksi kalıbına iki değişiklik ekliyoruz:
- Bir aday seçildikten sonra özyineleme
i + 1ile değiliile devam eder. Böylece aynı aday yeniden seçilebilir ama daha önceki bir adaya asla dönülmez:[2 2 3]üretilir,[3 2 2]üretilmez. - Adaylar sıralıysa ve
c[i]kalan toplamdan büyükse sonraki adaylar da büyüktür;continueyerine doğrudanbreakile döngüden çıkabiliriz. Bu bir sınır budamasıdır.
[2, 3, 6, 7] ve hedef 7 için gezilen ağacın tamamı şöyle:
kalan 7
├── 2 → kalan 5
│ ├── 2 → kalan 3
│ │ ├── 2 → kalan 1
│ │ │ └── 2 > 1, dur
│ │ ├── 3 → kalan 0: [2 2 3] bulundu
│ │ └── 6 > 3, dur
│ ├── 3 → kalan 2
│ │ └── 3 > 2, dur
│ └── 6 > 5, dur
├── 3 → kalan 4
│ ├── 3 → kalan 1
│ │ └── 3 > 1, dur
│ └── 6 > 4, dur
├── 6 → kalan 1
│ └── 6 > 1, dur
└── 7 → kalan 0: [7] bulunduHer "dur" satırı bir break'tir: o düğümün geri kalan bütün çocukları tek bir karşılaştırmayla elenir.
package main
import (
"fmt"
"slices"
)
func combinationSum(candidates []int, target int) [][]int {
c := slices.Sorted(slices.Values(candidates))
var result [][]int
var path []int
var backtrack func(start, remain int)
backtrack = func(start, remain int) {
if remain == 0 {
result = append(result, slices.Clone(path))
return
}
for i := start; i < len(c); i++ {
if c[i] > remain {
break // sıralı olduğu için sonrakiler de büyük
}
path = append(path, c[i])
backtrack(i, remain-c[i]) // i: aynı aday yeniden seçilebilir
path = path[:len(path)-1]
}
}
backtrack(0, target)
return result
}
func main() {
fmt.Println(combinationSum([]int{2, 3, 6, 7}, 7))
fmt.Println(combinationSum([]int{2, 3, 5}, 8))
fmt.Println(combinationSum([]int{2}, 1))
}[[2 2 3] [7]] [[2 2 2 2] [2 3 3] [3 5]] []
Kombinasyon toplamı II: her aday bir kez, tekrarlar atlanır
Problem: Bu kez candidates tekrar eden değerler içerebilir ve her eleman en fazla bir kez kullanılabilir. Sonuçta aynı kombinasyon birden fazla kez yer almamalı. [10, 1, 2, 7, 6, 1, 5] ve hedef 8 için cevap: [1 1 6], [1 2 5], [1 7], [2 6].
Bir elemanı yeniden kullanmamak için özyineleme i + 1 ile devam eder. Tekrarlardan kurtulmak için yine sıralayıp atlarız, ama koşul permütasyonlardakinden farklıdır:
if i > start && c[i] == c[i-1] {
continue // bu düzeyde aynı değer zaten denendi
}Sıralı dizi [1 1 2 5 6 7 10] üzerinde düşünelim. Kök düzeyinde (start = 0) ilk 1 denendiğinde, ikinci 1 ile başlayabilecek her kombinasyon zaten ilk 1 ile başlayanların arasında üretilmiştir; bu düzeyde ikinci 1 atlanmalıdır. Ama ilk 1 seçildikten sonraki düzeyde (start = 1) ikinci 1, o düzeyin ilk adayıdır ve seçilebilmelidir; aksi hâlde [1 1 6] kaybolur. i > start koşulu tam olarak bunu söyler: "aynı düzeyde, aynı değeri ikinci kez deneme".
package main
import (
"fmt"
"slices"
)
func combinationSum2(candidates []int, target int) [][]int {
c := slices.Sorted(slices.Values(candidates))
var result [][]int
var path []int
var backtrack func(start, remain int)
backtrack = func(start, remain int) {
if remain == 0 {
result = append(result, slices.Clone(path))
return
}
for i := start; i < len(c); i++ {
if c[i] > remain {
break // sınır budaması
}
if i > start && c[i] == c[i-1] {
continue // tekrar budaması
}
path = append(path, c[i])
backtrack(i+1, remain-c[i]) // i+1: her eleman en fazla bir kez
path = path[:len(path)-1]
}
}
backtrack(0, target)
return result
}
func main() {
fmt.Println(combinationSum2([]int{10, 1, 2, 7, 6, 1, 5}, 8))
fmt.Println(combinationSum2([]int{2, 5, 2, 1, 2}, 5))
}[[1 1 6] [1 2 5] [1 7] [2 6]] [[1 2 2] [5]]
Buraya kadar gördüğümüz varyantlar küçük ama kritik farklarla ayrılıyor. Bir mülakatta hangi satırın değişmesi gerektiğini hızla çıkarabilmek için bu tabloyu iyice sindir:
N-Vezir problemi
Problem: n × n boyutlu bir satranç tahtasına n veziri, hiçbiri diğerini tehdit etmeyecek şekilde yerleştir. Bir vezir aynı satırdaki, aynı sütundaki ve iki çapraz doğrultudaki bütün kareleri tehdit eder. Kaç farklı yerleşim vardır?
Kaba kuvvetle 8 × 8 tahtanın 64 karesinden 8'ini seçmenin C(64, 8) = 4.426.165.368 yolu vardır. Oysa küçük bir gözlem arama uzayını dramatik biçimde daraltır: her satırda tam olarak bir vezir bulunmak zorundadır. O hâlde kararları satır satır veririz: "0. satırdaki vezir hangi sütunda? 1. satırdaki hangi sütunda?" Aynı satırda iki vezir olması yapı gereği imkânsız hâle gelir; geriye sütunları ve çaprazları kontrol etmek kalır.
Aşağıdaki görselleştirmede 6 × 6 tahtada vezirlerin satır satır yerleştirilişini adım adım izle. Bir satırda hiçbir güvenli sütun kalmadığı ve önceki satırdaki vezirin geri alındığı anlara özellikle dikkat et: geri izleme tam olarak o anlarda gerçekleşiyor.
Çaprazları O(1)'de kontrol etmek: row-col ve row+col
Yeni bir veziri koyarken önceki bütün vezirleri tek tek kontrol etmek O(n) sürer. Bunun yerine hangi sütunların ve çaprazların dolu olduğunu boolean dilimlerde tutarsak kontrol O(1)'e iner. Sütunlar kolay: cols[col]. Peki bir çaprazı tek bir sayıyla nasıl adlandırırız?
- Sol üstten sağ alta inen (↘) bir çaprazda satır ve sütun birlikte artar, dolayısıyla
row - colsabittir. - Sağ üstten sol alta inen (↙) bir çaprazda satır artarken sütun azalır, dolayısıyla
row + colsabittir.
row - col (↘ çaprazlar) row + col (↙ çaprazlar)
c=0 c=1 c=2 c=3 c=0 c=1 c=2 c=3
r=0 0 -1 -2 -3 r=0 0 1 2 3
r=1 1 0 -1 -2 r=1 1 2 3 4
r=2 2 1 0 -1 r=2 2 3 4 5
r=3 3 2 1 0 r=3 3 4 5 6Aynı sayıyı taşıyan kareler aynı çapraz üzerindedir. row - col değeri −(n−1) ile n−1 arasında değişir; negatif indeks kullanamayacağımız için buna n - 1 ekleyip 0 ile 2n−2 arasına kaydırırız. row + col zaten 0 ile 2n−2 arasındadır. Böylece iki çapraz ailesinin her biri 2n−1 uzunluğunda bir dilimle temsil edilir. Örneğin (1, 2) karesindeki bir vezir row - col = -1 çaprazını ve row + col = 3 ters çaprazını kapatır; bu yüzden (0, 1) karesi ilk çapraz, (3, 0) karesi de ikinci çapraz üzerinden tehdit altındadır.
package main
import (
"fmt"
"strings"
)
// solveNQueens çözüm sayısını döndürür; visit nil değilse her çözümde çağrılır.
func solveNQueens(n int, visit func(queens []int)) int {
queens := make([]int, n) // queens[row]: o satırdaki vezirin sütunu
cols := make([]bool, n) // sütun dolu mu?
diag := make([]bool, 2*n-1) // row-col+n-1 çaprazı (↘) dolu mu?
anti := make([]bool, 2*n-1) // row+col çaprazı (↙) dolu mu?
count := 0
var place func(row int)
place = func(row int) {
if row == n {
count++
if visit != nil {
visit(queens)
}
return
}
for col := range n {
d, a := row-col+n-1, row+col
if cols[col] || diag[d] || anti[a] {
continue // kare tehdit altında: budama
}
queens[row] = col
cols[col], diag[d], anti[a] = true, true, true // seç
place(row + 1) // keşfet
cols[col], diag[d], anti[a] = false, false, false // geri al
}
}
place(0)
return count
}
func printBoard(queens []int) {
n := len(queens)
for _, col := range queens {
fmt.Println(strings.Repeat(". ", col) + "V" + strings.Repeat(" .", n-col-1))
}
fmt.Println()
}
func main() {
fmt.Println("4 × 4 tahtanın çözümleri:")
solveNQueens(4, printBoard)
for n := 1; n <= 8; n++ {
fmt.Printf("n = %d: %d çözüm\n", n, solveNQueens(n, nil))
}
}4 × 4 tahtanın çözümleri: . V . . . . . V V . . . . . V . . . V . V . . . . . . V . V . . n = 1: 1 çözüm n = 2: 0 çözüm n = 3: 0 çözüm n = 4: 2 çözüm n = 5: 10 çözüm n = 6: 4 çözüm n = 7: 40 çözüm n = 8: 92 çözüm
Çıktı bilinen değerlerle uyuşuyor: n = 2 ve n = 3 için çözüm yok, n = 6'nın çözüm sayısı n = 5'inkinden az ve klasik 8 × 8 tahtada 92 çözüm var. visit fonksiyonuna verilen queens dilimi arama sürdükçe değişmeye devam eder; bir çözümü saklamak istersen yine slices.Clone kullanmalısın.
Neden doğru? Her satıra tam bir vezir konduğu ve her yerleştirme sütun ile iki çapraz için kontrol edildiği için bulunan her yerleşim geçerlidir. Hiçbir çözümün kaçırılmadığını görmek için şunu düşün: geçerli bir yerleşimin herhangi bir öneki (ilk birkaç satırı) da çakışma içermez. Budama yalnızca çakışma içeren önekleri keser, dolayısıyla hiçbir geçerli çözüme giden yol kesilmez. Algoritma her satırda güvenli olan bütün sütunları denediği için her geçerli yol sonuna kadar izlenir.
İlk satırda n seçenek, ikincide sütun kısıtı nedeniyle en fazla n−1 seçenek vardır ve bu böyle sürer; yaprak sayısı en fazla n! olur. Çapraz kısıtları gerçekte ağacı bundan çok daha fazla küçültür; bunu bir sonraki bölümde ölçeceğiz. Ek alan dört dilim ve n derinliğindeki çağrı yığını için O(n)'dir.
Budama (pruning)
Budama, kısmi bir çözümün hiçbir geçerli çözüme tamamlanamayacağını mümkün olduğunca erken fark edip o alt ağaca hiç inmemektir. Doğru bir budama sonucu değiştirmez; yalnızca gezilen düğüm sayısını azaltır. Bu derste karşılaştığımız türleri bir araya toplayalım:
Budamanın etkisini somut olarak görelim. Aşağıdaki program N-Vezir'i iki şekilde çözüyor: budamasız sürüm her satıra her sütunu koyar ve tahtayı yalnızca en sonda kontrol eder; budamalı sürüm her veziri koyar koymaz önceki satırlarla karşılaştırır ve çakışma varsa o dala hiç inmez. İki sürüm de aynı sayıda çözüm bulur ama search çağrı sayıları çok farklıdır:
package main
import "fmt"
// search row satırından itibaren vezirleri yerleştirir ve çözüm sayısını döndürür.
// prune true ise çakışan vezir hemen elenir; false ise tahta yalnızca sonda kontrol edilir.
func search(n, row int, queens []int, prune bool, calls *int) int {
*calls++
if row == n {
if prune || isValid(queens) {
return 1
}
return 0
}
count := 0
for col := range n {
queens[row] = col
if prune && !isSafe(queens, row) {
continue
}
count += search(n, row+1, queens, prune, calls)
}
return count
}
// isSafe row satırındaki vezirin önceki satırlardakilerle çakışmadığını kontrol eder.
func isSafe(queens []int, row int) bool {
for r := range row {
d := queens[row] - queens[r]
if d == 0 || d == row-r || d == r-row {
return false
}
}
return true
}
func isValid(queens []int) bool {
for row := range queens {
if !isSafe(queens, row) {
return false
}
}
return true
}
func main() {
fmt.Println("n çözüm budamasız çağrı budamalı çağrı")
for n := 4; n <= 8; n++ {
queens := make([]int, n)
var slow, fast int
a := search(n, 0, queens, false, &slow)
b := search(n, 0, queens, true, &fast)
if a != b {
panic("iki sürüm farklı sonuç verdi")
}
fmt.Printf("%d %5d %15d %14d\n", n, a, slow, fast)
}
}n çözüm budamasız çağrı budamalı çağrı 4 2 341 17 5 10 3906 54 6 4 55987 153 7 40 960800 552 8 92 19173961 2057
Bu kodda açık bir geri al satırı görmüyorsun, çünkü queens[row] döngünün bir sonraki turunda zaten üzerine yazılıyor ve isSafe yalnızca önceki satırlara bakıyor; eski değerin kalması hiçbir şeyi bozmuyor.
n = 8 için budamasız sürüm 1 + 8 + 8² + … + 8⁸ = 19.173.961 çağrı yapıyor, budamalı sürüm ise yalnızca 2.057; yaklaşık 9.300 kat daha az. Arada bir ara nokta da var: yalnızca sütunları erken kontrol edip çaprazları sona bıraksaydık ağaç bir permütasyon ağacına dönüşür ve n = 8 için 109.601 çağrı gerekirdi. Kural basit: kontrol ne kadar erken yapılırsa ağaç o kadar erken daralır.
Sudoku çözücü: genel bakış
Sudoku, geri izlemenin "tüm çözümleri listele" değil "bir çözüm bul" biçimine güzel bir örnektir. 9 × 9 tablonun her satırında, her sütununda ve her 3 × 3 kutusunda 1–9 rakamları birer kez bulunmalıdır. Algoritma şöyle çalışır:
- Tabloyu satır satır tarayarak ilk boş hücreyi bul. Boş hücre yoksa bulmaca çözülmüştür.
- Bu hücreye 1'den 9'a kadar, satırında, sütununda ve kutusunda bulunmayan her rakamı sırayla dene.
- Rakamı yerleştir ve bir sonraki boş hücre için özyinelemeli olarak devam et.
- Özyineleme
truedönerse çözüm bulunmuştur; hementruedöndür. - Hiçbir rakam işe yaramazsa hücreyi boş bırakıp
falsedöndür. Bu, çağıran düzeyin kendi rakamını geri alıp bir sonrakini denemesine yol açar.
Bir hücrenin hangi kutuda olduğunu bulmak için satırı ve sütunu 3'e bölüp birleştiririz:
kutu = (satır / 3) * 3 + sütun / 3
sütun 0-2 sütun 3-5 sütun 6-8
+---------+---------+---------+
0-2 | 0 | 1 | 2 |
+---------+---------+---------+
3-5 | 3 | 4 | 5 |
+---------+---------+---------+
6-8 | 6 | 7 | 8 |
+---------+---------+---------+Satırlar, sütunlar ve kutular için birer boolean tablo tutarak "bu rakam burada kullanılmış mı?" sorusunu O(1)'de cevaplıyoruz:
package main
import (
"fmt"
"strings"
)
type sudoku struct {
grid [9][9]int
rows [9][10]bool // rows[r][d]: r. satırda d rakamı var mı?
cols [9][10]bool
boxes [9][10]bool
calls int
}
// set (r, c) hücresine d rakamını yazar (on == true) ya da hücreyi boşaltır.
func (s *sudoku) set(r, c, d int, on bool) {
b := r/3*3 + c/3
s.rows[r][d], s.cols[c][d], s.boxes[b][d] = on, on, on
if on {
s.grid[r][c] = d
} else {
s.grid[r][c] = 0
}
}
func (s *sudoku) canPlace(r, c, d int) bool {
b := r/3*3 + c/3
return !s.rows[r][d] && !s.cols[c][d] && !s.boxes[b][d]
}
// solve pos = satır*9 + sütun konumundan itibaren boş hücreleri doldurur.
func (s *sudoku) solve(pos int) bool {
s.calls++
for pos < 81 && s.grid[pos/9][pos%9] != 0 {
pos++ // dolu hücreleri atla
}
if pos == 81 {
return true // boş hücre kalmadı
}
r, c := pos/9, pos%9
for d := 1; d <= 9; d++ {
if !s.canPlace(r, c, d) {
continue
}
s.set(r, c, d, true) // seç
if s.solve(pos + 1) { // keşfet
return true
}
s.set(r, c, d, false) // geri al
}
return false
}
func main() {
puzzle := [9]string{
"53..7....", "6..195...", ".98....6.",
"8...6...3", "4..8.3..1", "7...2...6",
".6....28.", "...419..5", "....8..79",
}
s := &sudoku{}
for r, line := range puzzle {
for c := range 9 {
if line[c] != '.' {
s.set(r, c, int(line[c]-'0'), true)
}
}
}
solved := s.solve(0)
fmt.Println("çözüldü:", solved, "| çağrı sayısı:", s.calls)
for r, row := range s.grid {
if r > 0 && r%3 == 0 {
fmt.Println("------+-------+------")
}
var sb strings.Builder
for c, d := range row {
if c > 0 && c%3 == 0 {
sb.WriteString("| ")
}
fmt.Fprintf(&sb, "%d ", d)
}
fmt.Println(strings.TrimSpace(sb.String()))
}
}çözüldü: true | çağrı sayısı: 4209 5 3 4 | 6 7 8 | 9 1 2 6 7 2 | 1 9 5 | 3 4 8 1 9 8 | 3 4 2 | 5 6 7 ------+-------+------ 8 5 9 | 7 6 1 | 4 2 3 4 2 6 | 8 5 3 | 7 9 1 7 1 3 | 9 2 4 | 8 5 6 ------+-------+------ 9 6 1 | 5 3 7 | 2 8 4 2 8 7 | 4 1 9 | 6 3 5 3 4 5 | 2 8 6 | 1 7 9
solve bir bool döndürüyor ve ilk çözüm bulunduğunda geri al adımına hiç uğramadan true değeri yukarı taşınıyor; böylece çözülmüş tablo grid içinde kalıyor. Bu, listeleme problemlerinden önemli bir farktır: orada her sonuçtan sonra aramaya devam edebilmek için mutlaka geri alırız. Ayrıca solved değişkenini ayrı bir satırda hesapladığımıza dikkat et: fmt.Println(s.solve(0), s.calls) yazsaydık, Go belirtimi fonksiyon çağrısı ile alan okuması arasındaki değerlendirme sırasını garanti etmediği için s.calls değerinin çağrıdan önce mi sonra mı okunacağı belirsiz olurdu.
En kötü durumda m boş hücre için 9ᵐ olasılık vardır, ama kısıtlar ağacı çok erken budar: bu bulmacanın 51 boş hücresi birkaç bin çağrıda dolduruluyor. Daha zor bulmacalar için iki klasik iyileştirme vardır: boş hücreleri sırayla değil en az adayı olan hücreden başlayarak doldurmak (MRV, minimum remaining values) ve bir hücreye rakam yazıldığında komşu hücrelerin aday kümelerini hemen güncellemek (kısıt yayılımı, constraint propagation). İkisi de sonucu değiştirmez; yalnızca ağacı küçültür.
Izgarada kelime arama
Problem: Harflerden oluşan bir ızgara ve bir kelime veriliyor. Kelime, yatay veya dikey komşu hücrelerden art arda geçilerek yazılabiliyor mu? Aynı hücre bir kelimede en fazla bir kez kullanılabilir.
K E D İ
A Ç A Y
L E M ABu ızgarada KEDİ (ilk satır), ÇAM (Ç → sağdaki A → aşağıdaki M) ve KALEM (K → aşağı A → aşağı L → sağ E → sağ M) yazılabilir. ADA ise yazılamaz: D'ye komşu olan tek A, (1, 2) hücresindeki A'dır ve kelimenin hem ilk hem son harfi için aynı hücreyi kullanamayız.
Çözüm, her hücreden başlayan bir derinlik öncelikli aramadır. Kelimenin k. harfi hücreyle eşleşirse hücreyi "kullanıldı" diye işaretler (seç), dört komşuda k+1. harfi ararız (keşfet), sonra hücrenin eski harfini geri koyarız (geri al). Türkçe harfler UTF-8'de birden fazla bayt tuttuğu için ızgarayı ve kelimeyi []rune olarak işliyoruz.
package main
import "fmt"
func exist(board [][]rune, word string) bool {
w := []rune(word)
rows, cols := len(board), len(board[0])
var dfs func(r, c, k int) bool
dfs = func(r, c, k int) bool {
if k == len(w) {
return true // bütün harfler eşleşti
}
if r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] != w[k] {
return false
}
saved := board[r][c]
board[r][c] = '#' // seç: hücreyi kullanılmış olarak işaretle
found := dfs(r+1, c, k+1) || dfs(r-1, c, k+1) ||
dfs(r, c+1, k+1) || dfs(r, c-1, k+1) // keşfet
board[r][c] = saved // geri al
return found
}
for r := range rows {
for c := range cols {
if dfs(r, c, 0) {
return true
}
}
}
return false
}
func main() {
lines := []string{"KEDİ", "AÇAY", "LEMA"}
board := make([][]rune, len(lines))
for i, line := range lines {
board[i] = []rune(line)
}
for _, word := range []string{"KEDİ", "ÇAM", "KALEM", "ADA"} {
fmt.Printf("%-6s %v\n", word, exist(board, word))
}
}KEDİ true ÇAM true KALEM true ADA false
Geri al adımı burada da vazgeçilmez: işareti geri koymasaydık bir aramada kullanılan hücreler # olarak kalır, sonraki başlangıç noktaları ve sonraki kelimeler için tahta bozulurdu. İşaret koymasaydık da ADA için aynı A hücresi iki kez kullanılır ve yanlışlıkla true dönerdi. || operatörünün kısa devre yapması sayesinde kelime bulunduğu anda kalan yönler denenmez. %-6s biçimlendirmesinin genişliği bayt değil rune sayısıyla ölçtüğüne de dikkat et; KEDİ bu yüzden düzgün hizalanıyor.
R × C başlangıç hücresinin her birinden ilk adımda 4, sonraki adımlarda en fazla 3 yöne gidilebilir, çünkü geldiğimiz hücre işaretlidir. L kelimenin uzunluğudur ve özyineleme derinliği de L ile sınırlıdır. Bu problemin yapısı BFS ve DFS dersindeki ızgara gezinmesine çok benzer. Fark şu: ada saymada ziyaret işareti kalıcıdır, çünkü bir hücreyi bir kez görmek yeter; kelime aramada ise işaret geri alınır, çünkü aynı hücre başka bir yolun parçası olarak yeniden kullanılabilir.
Karmaşıklık analizi
Geri izleme algoritmalarının zaman karmaşıklığı kabaca (ağaçtaki düğüm sayısı) × (düğüm başına iş) olarak hesaplanır. Dallanma faktörü b ve derinlik d ise düğüm sayısı O(bᵈ) ile sınırlıdır. Bu dersteki problemleri bir arada görelim:
Kombinasyon toplamı satırında T hedef değeri, m en küçük adaydır: her seçim kalan toplamı en az m azalttığı için yol en fazla T / m uzunluğunda olabilir.
Bu tablodan çıkarılacak iki önemli ders var:
- Çıktının boyutu bir alt sınırdır. 20 elemanın tüm alt kümelerini listelemek istiyorsan 2²⁰ = 1.048.576 sonucu üretmek zorundasın; hiçbir algoritma çıktıyı yazmaktan hızlı olamaz. Listeleme problemlerinde üstel süre bir tasarım hatası değil, problemin doğasıdır.
- Girdi sınırları hızla yaklaşır. 2³⁰ bir milyarı aşar; 10! = 3.628.800 iken 12! = 479.001.600'dür. Kabaca, alt küme tabanlı aramalar n ≈ 20 civarına, permütasyon tabanlı aramalar n ≈ 10 civarına kadar rahat çalışır. Budama bu sınırları pratikte yukarı iter ama en kötü durumu ortadan kaldırmaz.
Geri izleme ne zaman kullanılır?
Bir problemle karşılaştığında önce sorunun ne istediğine bak:
Örneğin "toplamı 7 olan kombinasyonları listele" geri izleme gerektirir. Ama "toplamı 7 olan kaç kombinasyon var?" sorusu, aynı alt problemleri ("kalan toplam 3 iken kaç yol var?") defalarca çözdüğü için dinamik programlamayla polinom zamanda cevaplanır. Her adımda güvenle tek bir seçim yapabildiğin problemlerde ise açgözlü algoritmalar arama yapmadan sonuca gider. Geri izleme; seçimlerin birbirini karmaşık biçimde kısıtladığı, bütün çözümlerin istendiği veya başka bir yapının bulunmadığı durumlar için güvenilir bir son çaredir.
Sık yapılan hatalar
pathdilimini kopyalamadan sonuca eklemek. Bütün sonuçlar aynı alttaki diziyi paylaşır ve arama bittiğinde anlamsız değerler görürsün. Her zamanslices.Clone(path)kullan.- Geri al adımını eksik yapmak. Seçte iki şey değiştirdiysen (
used[i]vepath) ikisini de geri al. Özellikle döngü içinde erkenreturnveyacontinueeklerken seçilmiş ama geri alınmamış bir durum bırakmadığından emin ol. - Kombinasyonlarda başlangıç indeksini unutmak. Döngüyü her seferinde 0'dan başlatırsan
[1 2]ile[2 1]iki ayrı sonuç olarak üretilir; kombinasyon yerine permütasyon elde edersin. iilei + 1'i karıştırmak. Kombinasyon toplamında (sınırsız kullanım) özyinelemeiile, kombinasyon toplamı II'de (tek kullanım)i + 1ile devam eder. Yanlış olanı yazmak ya eksik ya da fazladan sonuç üretir.- Tekrar atlama kuralını sıralamadan kullanmak.
c[i] == c[i-1]karşılaştırması eşit değerlerin yan yana olduğunu varsayar; girdiyi sıralamazsan tekrarlar yakalanmaz. i > startyerinei > 0yazmak. Kombinasyon toplamı II'de bu, alt düzeydeki meşru tekrarları da eler ve[1 1 6]gibi sonuçlar kaybolur.- Sıralanmamış girdide
breakile budamak.c[i] > remainolduğundabreakyalnızca sonraki adaylar daha büyükse doğrudur; aksi hâlde geçerli kombinasyonları sessizce kaybedersin. - İşareti geri koymamak. Izgara problemlerinde hücreyi
#yapıp eski değerine döndürmezsen tahta sonraki aramalar için bozulur.
Alıştırmalar
n uzunluğundaki, içinde iki 1 yan yana gelmeyen tüm ikili dizgeleri (yalnızca 0 ve 1) sözlük sırasıyla üret. n = 4 için 8 dizge vardır: 0000, 0001, 0010, 0100, 0101, 1000, 1001, 1010. Ayrıca n = 1…6 için dizge sayılarını yazdır.
İpucu
Her konumda iki seçenek var: 0 her zaman eklenebilir, 1 ise yalnızca bir önceki karakter 1 değilse. Önce 0 dalını denersen sonuçlar kendiliğinden sözlük sırasında çıkar.
Çözümü göster
package main
import "fmt"
func binaryStrings(n int) []string {
var result []string
path := make([]byte, 0, n)
var backtrack func()
backtrack = func() {
if len(path) == n {
result = append(result, string(path)) // string(...) baytları kopyalar
return
}
path = append(path, '0')
backtrack()
path = path[:len(path)-1]
if len(path) == 0 || path[len(path)-1] != '1' { // budama: "11" oluşmasın
path = append(path, '1')
backtrack()
path = path[:len(path)-1]
}
}
backtrack()
return result
}
func main() {
fmt.Println(binaryStrings(4))
var counts []int
for n := 1; n <= 6; n++ {
counts = append(counts, len(binaryStrings(n)))
}
fmt.Println(counts)
}[0000 0001 0010 0100 0101 1000 1001 1010] [2 3 5 8 13 21]
Budama geçersiz dalları ilk 11 oluştuğu anda kestiği için ağaçta hiç çıkmaz yol kalmaz; gezilen düğüm sayısı sonuç sayısıyla orantılıdır. Sayıların Fibonacci dizisini izlediğine dikkat et: n uzunluğundaki geçerli dizgeler ya 0 ile biten n−1 uzunluklu bir dizgeden ya da 01 ile biten n−2 uzunluklu bir dizgeden gelir. Sonuç sayısı F(n+2) ≈ 1,618ⁿ hızında büyüdüğü için zaman karmaşıklığı O(n · 1,618ⁿ), ek alan O(n)'dir. Aynı sayıyı listelemeden bulmak ise tam bir dinamik programlama problemidir.
n çift parantezle yazılabilecek tüm dengeli parantez dizilimlerini üret. n = 3 için 5 dizilim vardır: ((())), (()()), (())(), ()(()), ()()(). Ayrıca n = 1…6 için dizilim sayılarını yazdır.
İpucu
Şimdiye kadar kaç açma ve kaç kapama parantezi kullandığını izle. Açma parantezi opened < n iken, kapama parantezi ise yalnızca closed < opened iken eklenebilir. Bu iki kural her önekin geçerli kalmasını garanti eder.
Çözümü göster
package main
import "fmt"
func generateParentheses(n int) []string {
var result []string
path := make([]byte, 0, 2*n)
var backtrack func(opened, closed int)
backtrack = func(opened, closed int) {
if len(path) == 2*n {
result = append(result, string(path))
return
}
if opened < n {
path = append(path, '(')
backtrack(opened+1, closed)
path = path[:len(path)-1]
}
if closed < opened {
path = append(path, ')')
backtrack(opened, closed+1)
path = path[:len(path)-1]
}
}
backtrack(0, 0)
return result
}
func main() {
fmt.Println(generateParentheses(3))
var counts []int
for n := 1; n <= 6; n++ {
counts = append(counts, len(generateParentheses(n)))
}
fmt.Println(counts)
}[((())) (()()) (())() ()(()) ()()()] [1 2 5 14 42 132]
Kaba kuvvet 2²ⁿ dizgenin tamamını üretip her birini kontrol ederdi. Burada iki kural, dengesiz olacak her öneki oluştuğu anda eler; ağaçtaki her yol geçerli bir sonuca ulaşır. Sonuç sayıları Catalan sayılarıdır ve Cₙ yaklaşık 4ⁿ / (n^1,5 · √π) hızında büyür. Her sonucun 2n uzunluğunda kopyalanması eklendiğinde zaman O(n · Cₙ) = O(4ⁿ / √n), ek alan O(n) olur.
Bir s dizgesini, her parçası palindrom olacak şekilde bölmenin tüm yollarını döndür. "aab" için cevap [a a b] ve [aa b]; "kabak" için [k a b a k], [k aba k] ve [kabak]'tır. Dizgenin yalnızca ASCII karakterlerden oluştuğunu varsayabilirsin.
İpucu
backtrack(start), s[start:] bölümünü parçalara ayırır. end değerini start + 1'den len(s)'e kadar dene; s[start:end] palindromsa onu yola ekle ve backtrack(end) çağır. Palindrom olmayan önekler budanır.
Çözümü göster
package main
import (
"fmt"
"slices"
)
func partition(s string) [][]string {
var result [][]string
var path []string
var backtrack func(start int)
backtrack = func(start int) {
if start == len(s) {
result = append(result, slices.Clone(path))
return
}
for end := start + 1; end <= len(s); end++ {
if !isPalindrome(s[start:end]) {
continue // budama: bu parça palindrom değil
}
path = append(path, s[start:end])
backtrack(end)
path = path[:len(path)-1]
}
}
backtrack(0)
return result
}
func isPalindrome(s string) bool {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
func main() {
fmt.Println(partition("aab"))
fmt.Println(partition("kabak"))
fmt.Println(len(partition("aaaaaaaa")), "bölümleme")
}[[a a b] [aa b]] [[k a b a k] [k aba k] [kabak]] 128 bölümleme
n uzunluğunda bir dizgenin n−1 kesme noktası vardır ve her biri kesilebilir veya kesilmeyebilir; bu yüzden en fazla 2ⁿ⁻¹ bölümleme olabilir. "aaaaaaaa" gibi bir dizgede bunların hepsi geçerlidir (2⁷ = 128). Her düğümde palindrom kontrolü ve kopyalama O(n) sürdüğünden en kötü durumda zaman O(n · 2ⁿ), ek alan O(n)'dir. Palindrom kontrollerini önceden bir DP tablosunda hesaplarsan her kontrol O(1)'e iner. Türkçe karakterli dizgeler için s yerine []rune(s) üzerinde çalışman gerekir.
Pozitif tamsayılardan oluşan nums dilimi ve bir k veriliyor. Diliminin elemanlarını, her birinin toplamı eşit olan k boş olmayan alt kümeye bölmek mümkün mü? Örnekler:
[4 3 2 3 5 2 1], k = 4 →true([5],[4 1],[3 2],[3 2])[1 2 3 4], k = 3 →false(toplam 10, 3'e bölünmüyor)[2 2 2 2 3 4 5], k = 4 →false(hedef 5, ama 4'ü tamamlayacak 1 yok)[10 10 10 7 7 7 7 7 7 6 6 6], k = 3 →true
İpucu
Toplam k'ya bölünmüyorsa cevap hemen false'tur. Aksi hâlde hedef total / k olur. k tane "kova" tut ve her sayıyı sırayla, hedefi aşmayacak bir kovaya koymayı dene. İki güçlü budama: sayıları büyükten küçüğe sırala (büyük sayılar çıkmazları erken ortaya çıkarır) ve aynı doluluğa sahip iki kovadan yalnızca birini dene, çünkü ikisi birbirinin simetriğidir.
Çözümü göster
package main
import (
"fmt"
"slices"
)
func canPartitionKSubsets(nums []int, k int) bool {
total := 0
for _, x := range nums {
total += x
}
if total%k != 0 {
return false
}
target := total / k
sorted := slices.Sorted(slices.Values(nums))
slices.Reverse(sorted) // büyükten küçüğe: çıkmazlar erken görünür
if sorted[0] > target {
return false
}
buckets := make([]int, k)
var place func(i int) bool
place = func(i int) bool {
if i == len(sorted) {
return true // hiçbir kova hedefi aşmadı ve toplam k*target: hepsi eşit
}
for b := range k {
if buckets[b]+sorted[i] > target {
continue
}
if b > 0 && buckets[b] == buckets[b-1] {
continue // simetri: aynı doluluktaki önceki kova zaten denendi
}
buckets[b] += sorted[i] // seç
if place(i + 1) { // keşfet
return true
}
buckets[b] -= sorted[i] // geri al
}
return false
}
return place(0)
}
func main() {
fmt.Println(canPartitionKSubsets([]int{4, 3, 2, 3, 5, 2, 1}, 4))
fmt.Println(canPartitionKSubsets([]int{1, 2, 3, 4}, 3))
fmt.Println(canPartitionKSubsets([]int{2, 2, 2, 2, 3, 4, 5}, 4))
fmt.Println(canPartitionKSubsets([]int{10, 10, 10, 7, 7, 7, 7, 7, 7, 6, 6, 6}, 3))
}true false false true
Her sayı k kovadan birine gidebildiği için arama ağacının kaba üst sınırı O(kⁿ)'dir; ek alan O(n + k). Simetri budaması bu ağacı büyük ölçüde daraltır: kovalar birbirinin yerine geçebildiği için, aynı doluluktaki iki kovadan birine konan sayı ötekine konmuşla aynı durumu üretir. Bu kural sayesinde boş kovalar hep sonda toplanır ve ilk sayı yalnızca ilk kovaya konur. Sayıları büyükten küçüğe sıralamak da çıkmazları ağacın üst düzeylerinde ortaya çıkarır. i == len(sorted) durumunda ayrıca kontrol gerekmez: hiçbir kova hedefi aşmadığı ve toplam tam k * target olduğu için bütün kovalar hedefe eşittir.
Kısa sınav
Kapasitesi 3 olan path ile sırasıyla path = append(path, 1), res = append(res, path), path = path[:0], path = append(path, 2), res = append(res, path) çalıştırılıyor. fmt.Println(res) ne yazdırır?
n farklı elemanın bütün permütasyonlarını listeleyen geri izleme algoritmasının zaman karmaşıklığı nedir?
8 × 8 tahtada (2, 5) karesinde bir vezir var (satır, sütun). Aşağıdaki karelerden hangisi bu vezir tarafından çapraz olarak tehdit edilir?
Kombinasyon toplamında (adaylar sınırsız kullanılabilir) özyinelemeli çağrı neden backtrack(i + 1, ...) değil de backtrack(i, remain - c[i]) biçimindedir?
Kombinasyon toplamı II'de sıralı adaylar [1 1 2 5 6 7 10] ve hedef 8. Atlama koşulu i > start yerine i > 0 yazılırsa hangi sonuç kaybolur?
Kombinasyon toplamında adayları sıralamadan if c[i] > remain { break } budaması kullanılırsa ne olur?
Özet
- Geri izleme, kararların oluşturduğu örtük bir ağacı derinlik öncelikli gezer; bellekte yalnızca kökten mevcut düğüme kadar olan yol durur.
- Her çözüm aynı iskelete oturur: tamamlandıysa kaydet; her aday için geçerliyse seç, keşfet, geri al. Doğruluk, "çağrı dönünce durum eski hâlindedir" değişmezine dayanır.
- Alt kümeler için "dahil et / etme" ve "başlangıç indeksi" kalıpları vardır; kombinasyon ve hedef toplam problemleri ikincisinin küçük varyasyonlarıdır (
iveyai + 1,break, tekrar atlama). - Tekrarlı girdilerde önce sırala, sonra aynı düzeyde aynı değeri ikinci kez deneme: permütasyonlarda
!used[i-1], kombinasyonlardai > startkoşulu. - N-Vezir'de satır satır yerleştirme ve
row - col,row + colindeksleri çakışma kontrolünü O(1)'e indirir; n = 8 için 92 çözüm vardır. - Budama sonucu değiştirmeden ağacı küçültür: N-Vezir'de n = 8 için 19 milyonu aşan çağrı 2.057'ye iner. Ama en kötü durum çoğu zaman üstel kalır.
- Go'da sonuca her zaman
slices.Clone(path)ekle; dilim başlığını saklamak bütün sonuçların aynı diziyi paylaşmasına yol açar. - Karmaşıklık kabaca düğüm sayısı × düğüm başına iştir: alt kümeler O(n · 2ⁿ), permütasyonlar O(n · n!); listeleme problemlerinde çıktının boyutu kaçınılmaz bir alt sınırdır.