Co to jest wycofywanie?

Question

Accepted Answer

**Wycofywanie** buduje kandydujące rozwiązania inkrementalnie i **porzuca** (cofa się) z częściowego kandydata tak szybko, jak tylko nie może on prowadzić do ważnego rozwiązania. Systematycznie eksploruje przestrzeń rozwiązań poprzez DFS, ocinając ślepe zaułki.

## Idea

Wybierz -> eksploruj -> usuń wybór. Spróbuj opcję, rekurencja; jeśli się nie powiedzie, cofnij ją i spróbuj następną.

## Przykład: wszystkie permutacje

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

## Klasyczne problemy

- **N-hetmanów**, Sudoku, wycieczka rycerza.
- **Podzbiory / kombinacje / permutacje.**
- **Wyszukiwanie słów**, rozwiązywanie labiryntu.

## Złożoność

Często wykładnicza (np. O(n!) dla permutacji), ale **obcinanie** drastycznie zmniejsza praktyczne wyszukiwanie.

## Kiedy użyć / pułapki

Używaj do spełniania ograniczeń i problemów "znajdź wszystkie ważne konfiguracje". Kluczowym wygrana jest **wczesne obcinanie** — pomiń gałęzie, które naruszają ograniczenia. Zapomnienie cofnięcia stanu ("usuń wybór") to klasyczny błąd.

## Dlaczego to ważne

Wycofywanie to systematyczny sposób eksploracji przestrzeni kombinatorycznych bez pomijania lub powtarzania kandydatów.

Dobre obcinanie zmienia niemożliwą siłę brutto w coś, co kończy się na czas.

Zapewnia moc rozwiązaniom dla łamigłówek, planowania i problemów z ograniczeniami w całej branży.