Ce este backtracking?

Question

Accepted Answer

**Backtracking** construiește soluții candidate incremental și **abandoneaza** (se retrage din) un candidat parțial de îndată ce acesta nu poate duce la o soluție validă. Explorează sistematic spațiul de soluții prin DFS, tăind capete moarte.

## Ideea

Alege -> explorează -> dezalege. Încearcă o opțiune, recursează; dacă eșuează, anulează și încearcă următoarea.

## Exemplu: toate permutările

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

## Probleme clasice

- **N-regine**, Sudoku, turul calului.
- **Subseturi / combinații / permutări.**
- **Căutare de cuvinte**, rezolvarea labirintului.

## Complexitate

Adesea exponențială (de ex., O(n!) pentru permutări), dar **tăierea** reduce dramatic căutarea practică.

## Când să folosești / capcane

Folosește pentru satisfacerea constrângerilor și problemele "găsește toate configurațiile valide". Câștigul principal este **tăierea timpurie** — sari peste ramuri care încalcă constrângerile. A uita să anulezi starea ("dezalege") este bug-ul clasic.

## De ce este important

Backtracking este modul sistematic de a explora spații combinatoriale fără a rata sau repeta candidații.

Tăierea bună transformă o forță brută inextricabilă în ceva care se termină la timp.

Alimentează rezolvitori pentru puzzle-uri, planificare și probleme de constrângere în toate industriile.