Apa itu backtracking?

Question

Accepted Answer

**Backtracking** membangun solusi kandidat secara bertahap dan **meninggalkan** (mundur) dari kandidat parsial segera setelah tidak dapat menghasilkan solusi yang valid. Ini secara sistematis menjelajahi ruang solusi melalui DFS, memangkas jalan buntu.

## Idenya

Pilih -> jelajahi -> batalkan pilihan. Coba satu opsi, rekursi; jika gagal, batalkan dan coba opsi berikutnya.

## Contoh: semua permutasi

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## Masalah klasik

- **N-ratu**, Sudoku, tur kuda.
- **Subset / kombinasi / permutasi.**
- **Pencarian kata**, pemecahan labirin.

## Kompleksitas

Sering kali eksponensial (mis., O(n!) untuk permutasi), tetapi **pemangkasan** mengurangi pencarian praktis secara dramatis.

## Kapan menggunakan / jebakan

Gunakan untuk masalah kepuasan kendala dan masalah "temukan semua konfigurasi valid". Keuntungan utamanya adalah **pemangkasan awal** — lewati cabang yang melanggar kendala. Lupa membatalkan status ("batalkan pilihan") adalah bug klasik.

## Mengapa ini penting

Backtracking adalah cara sistematis untuk menjelajahi ruang kombinatorial tanpa kehilangan atau mengulangi kandidat.

Pemangkasan yang baik mengubah kekerasan brute force yang tidak dapat ditangani menjadi sesuatu yang selesai tepat waktu.

Ia memberdayakan pemecah untuk teka-teki, penjadwalan, dan masalah kendala di seluruh industri.