バックトラッキングとは何ですか？

Question

バックトラッキングとは何ですか？

Accepted Answer

**バックトラッキング**は候補解をインクリメンタルに構築し、有効な解に至らない可能性が生じるとすぐに部分的な候補を**放棄**（バックトラック）します。DFSを通じてソリューション空間を体系的に探索し、デッドエンドを枝刈りします。

## 考え方

選択 -> 探索 -> 選択解除。オプションを試して再帰し、失敗したら元に戻して次を試します。

## 例：すべての順列

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

## 古典的な問題

- **N-queens**、数独、ナイトの一巡。
- **部分集合 / 組み合わせ / 順列。**
- **単語検索**、迷路解法。

## 計算量

しばしば指数関数的（例えば、順列の場合 O(n!)）ですが、**枝刈り**により実用的な探索が劇的に削減されます。

## 使用時期 / 落とし穴

制約充足と「すべての有効な構成を見つける」問題に使用します。重要な利点は**早期に枝刈り**することで、制約に違反するブランチをスキップします。状態を元に戻すこと（「選択解除」）を忘れるのは古典的なバグです。

## なぜ重要なのか

バックトラッキングは、候補を見逃したり繰り返したりすることなく、組み合わせ空間を探索する体系的な方法です。

良い枝刈りは手に負えないブルートフォースを実行可能な時間で完了できるものに変えます。

パズル、スケジューリング、および業界全体の制約問題のソルバーを支えています。