《アルゴリズムを学ぶ》12.全探索

# Overview
全探索（Brute Force Search） とは、すべての可能性を**力ずくで試す**アルゴリズム。
[1.選択ソートの基本](#1-選択ソートの基本)
[2.選択ソートの特徴](#2-選択ソートの特徴)
[3.典型問題を解いてみる](#3-典型問題を解いてみる)

# 1. 全探索のパターン
|探索方法	|説明	|使用例
|--|--|--
|1重ループ	|リストを1回スキャンする	|最大値、最小値探索
|2重ループ	|すべてのペアを調べる	|2つの和が条件を満たすペア探索
|3重ループ	|すべての3つ組を調べる	|3つの和が条件を満たす組み合わせ探索
|再帰的全探索（バックトラッキング）	|状態を保持しながら再帰で探索	|パス探索、ナップサック問題
|ビット全探索	|すべての部分集合を試す	|すべての組み合わせを列挙|


# 2. 1重ループを使った全探索
リストの中から 最大値 を求める。
```python
arr = [3, 1, 4, 1, 5, 9]
max_value = -float('inf')

for num in arr:
    max_value = max(max_value, num)

print(max_value)  # 9
```
ポイント:
・$O(N)$ でリスト全体を探索する
・最適化せずにシンプルに実装するのが全探索の基本

# 3. 2重ループを使った全探索
### (1) すべてのペアを探索
```python
arr = [1, 3, 5, 7]
for i in range(len(arr)):
    for j in range(i + 1, len(arr)):
        print(arr[i], arr[j])
```
ポイント:
・2つの要素の組み合わせを総当たりで試す
・$O(N²)$の計算量になる

### (2) 指定の条件を満たすペアを探す
例: 数列 A の中で、A[i] + A[j] = X となる (i, j) のペアを探す。

```python
A = [1, 2, 3, 4, 5]
X = 6

for i in range(len(A)):
    for j in range(i + 1, len(A)):
        if A[i] + A[j] == X:
            print(f"Pair: {A[i]}, {A[j]}")
```
ポイント:
・2重ループでペアをすべて試す
・より効率的な方法（ハッシュセットを使う）と比較できる

# 4. 3重ループを使った全探索
例: $A[i] + A[j] + A[k] = X$ となる (i, j, k) の組み合わせを探す。
```python
A = [1, 2, 3, 4, 5]
X = 6

for i in range(len(A)):
    for j in range(i + 1, len(A)):
        for k in range(j + 1, len(A)):
            if A[i] + A[j] + A[k] == X:
                print(f"Triplet: {A[i]}, {A[j]}, {A[k]}")
```
ポイント:
・3重ループで全パターンを探索
・$O(N³)$の計算量になるが、小さなデータセットなら問題ない

# 5. ビット全探索
例: N 個の要素のすべての部分集合を列挙する。

```python
A = [1, 2, 3]
N = len(A)

for bit in range(1 << N):  # 2^N 通りの部分集合
    subset = [A[i] for i in range(N) if bit & (1 << i)]
    print(subset)
```
ポイント:
・すべての部分集合を列挙
・$O(2^N)$の計算量なので N ≤ 20 程度まで


# 6. 典型問題を解いてみる

### 例題1. 2つの和が条件を満たすペア
**問題: N 個の整数が与えられる。A[i] + A[j] = X となる (i, j) のペアが存在するか判定せよ。**
> [参考： ABC315 B - Find Pair Sum](https://atcoder.jp/contests/abc315/tasks/abc315_b)
<details><summary> 回答　</summary>

```python
N, X = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
    for j in range(i + 1, N):
        if A[i] + A[j] == X:
            print("Yes")
            exit()
print("No")
```
</details>

### 例題2. 3つの和が条件を満たす組み合わせ
**問題: N 個の整数が与えられる。A[i] + A[j] + A[k] = X となる (i, j, k) の組み合わせを探せ。**
> [参考： ABC318 B - Find Triplet Sum](https://atcoder.jp/contests/abc318/tasks/abc318_b)
<details><summary> 回答　</summary>

```python
N, X = map(int, input().split())
A = list(map(int, input().split()))

for i in range(N):
    for j in range(i + 1, N):
        for k in range(j + 1, N):
            if A[i] + A[j] + A[k] == X:
                print(A[i], A[j], A[k])
```
</details>

### 例題3. ビット全探索
**問題: N 個の整数から、すべての部分集合の和を出力せよ。**
> [参考： ABC319 C - Subset Sum](https://atcoder.jp/contests/abc319/tasks/abc319_c)
<details><summary> 回答　</summary>

```python
N = int(input())
A = list(map(int, input().split()))

for bit in range(1 << N):
    subset_sum = sum(A[i] for i in range(N) if bit & (1 << i))
    print(subset_sum)
```
</details>

### 例題4. 文字列の全探索
**問題: 長さ N の文字列 S が与えられる。S に "abc" が含まれるか判定せよ。**
> [参考： ABC320 B - Find Substring](https://atcoder.jp/contests/abc320/tasks/abc320_b)
<details><summary> 回答　</summary>

```python
S = input()
N = len(S)

for i in range(N - 2):
    if S[i:i+3] == "abc":
        print("Yes")
        exit()
print("No")
```
</details>