Vad är backtracking?

Question

Accepted Answer

**Backtracking** bygger kandidatlösningar stegvis och **överger** (backtrackar från) en partiell kandidat så snart den inte kan leda till en giltig lösning. Det utforskar systematiskt lösningsrummet via DFS och prunar döda ändar.

## Idén

Välj -> utforska -> ångra. Prova ett alternativ, rekursera; om det misslyckas, ångra det och prova nästa.

## Exempel: alla permutationer

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

## Klassiska problem

- **N-damers problem**, Sudoku, springarens tur.
- **Delmängder / kombinationer / permutationer.**
- **Ordsökning**, labyrintlösning.

## Komplexitet

Ofta exponentiell (t.ex. O(n!) för permutationer), men **pruning** minskar den praktiska sökningen dramatiskt.

## När man använder / fallgropar

Används för begränsningsuppfyllelse och "hitta alla giltiga konfigurationer"-problem. Nyckelvinsten är **tidig pruning** — hoppa över grenar som bryter mot begränsningar. Att glömma att ångra tillståndet ("ångra") är klassiska buggen.

## Varför det spelar roll

Backtracking är det systematiska sättet att utforska kombinatoriska rum utan att missa eller upprepa kandidater.

God pruning förvandlar en omöjlig brute force till något som slutförs i tid.

Det driver lösare för pussel, schemaläggning och begränsningsproblem över hela industrin.