Što je backtracking?

Question

Accepted Answer

**Backtracking** gradi kandidatna rješenja inkrementalno i **odustaje** (vraća se unazad) od djelomičnog kandidata čim ne može dovesti do važećeg rješenja. Sistematski istražuje prostor rješenja pomoću DFS-a, preusmjeravajući mrtve završetke.

## Ideja

Odaberi -> istražite -> poništite izbor. Pokušajte opciju, rekurzirajte; ako ne uspije, poništite je i pokušajte sljedeću.

## Primjer: sva permutacija

```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
```

## Klasični problemi

- **N-kraljica**, Sudoku, jahačev obilazak.
- **Podskupovi / kombinacije / permutacije.**
- **Pretraživanje riječi**, rješavanje labirinta.

## Složenost

Često eksponencijalna (npr. O(n!) za permutacije), ali **preusmjeravanje** dramatično smanjuje praktičnu pretragu.

## Kada koristiti / zamke

Koristite za probleme zadovoljavanja ograničenja i "pronađite sve važeće konfiguracije". Ključna prednost je **rano preusmjeravanje** — preskočite grane koje narušavaju ograničenja. Zaboravljanje poništavanja stanja ("poništite izbor") je klasična greška.

## Zašto je važno

Backtracking je sistematičan način istraživanja kombinatornih prostora bez propuštanja ili ponavljanja kandidata.

Dobro preusmjeravanje pretvara neostvarljivu surovu silu u nešto što se završi na vrijeme.

Omogućuje riješenja za zagonetke, raspoređivanje i probleme ograničenja u cijeloj industriji.