Apa iku backtracking?

Question

Accepted Answer

**Backtracking** ngbangun solusi kandidat kanthi bertahap lan **ninggalake** (mundur saka) kandidat parsial sawise ora bisa dadi solusi sing sah. Iki nggali ruang solusi kanthi sistematis liwat DFS, ngpotong jalan buntu.

## Ideipun

Pilih -> gali -> batal pilihan. Coba siji opsi, rekursi; yen gagal, batal lan coba sing liya.

## Contoh: kabeh 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-queens**, Sudoku, tur kuda.
- **Subsets / kombinasi / permutasi.**
- **Word search**, pemecahan maze.

## Kompleksitas

Sadhela eksponensial (contone, O(n!) kanggo permutasi), nanging **pruning** ngpotong pencarian praktis kanthi drastis.

## Kapan nggunaake / jebakan

Gunakake kanggo masalah kepuasan kendala lan "golek kabeh konfigurasi sing sah". Kemenangan utamane yaiku **pruning awal** — lumpati cabang sing nerak kendala. Lali buat batal status ("batal pilihan") yaiku bug klasik.

## Apa sebabe penting

Backtracking yaiku cara sistematis kanggo nggali ruang kombinatorial tanpa ora keduman utawa ngulang kandidat.

Pruning sing apik ngubah brute force sing ora bisa dadi pangopalan dadi samubarang sing tuntas ing wektu.

Iki nggerakake solver kanggo puzzle, jadwal, lan masalah kendala ing saindhenging industri.