# 練習問題

## 知識の確認

### この順列アルゴリズムで結果が漏れないか

バックトラッキングのアルゴリズムが、`1、2、3` の順に選択を試し、全順列を生成しようとしています。数 `x` を選ぶたびに、次の処理を行います。

1. `x` を現在の経路の末尾に追加します。
2. `x` に「使用済み」の印を付けます。
3. 次の位置を再帰で埋めます。

再帰から戻った後、生徒は経路の末尾から `x` を削除するだけで、次の数を試しました。

<!-- numbered-subquestions -->

1. 最初にどの順列が得られますか。6 個すべての順列を得られますか。
2. 再帰で一つ上の層へ戻る前に、経路の末尾の数を削除するだけで十分ですか。不十分なら、ほかに何が必要ですか。理由も説明してください。

??? success "解答例"

    1. 最初に `[1, 2, 3]` が得られますが、全順列は得られません。戻ると経路は短くなりますが、
        1、2、3 の印はすべて「使用済み」のままなので、その後の分岐で選べる数がなくなります。

    2. 不十分です。末尾の `x` を削除した後、`x` の印を「未使用」に戻す必要があります。
        現在の経路と使用済みの印が、一緒に探索状態を表しています。選択時に二か所を変更したので、戻るときも両方を元に戻して初めて、
        ほかの分岐で `x` を再び選べます。

### 数を選ぶ順序は重要か

整列済み配列 `[2, 3, 5]` と目標値 5 が与えられ、各数は繰り返し選べます。
アルゴリズムでは、各探索経路の数が小さい順にだけ現れるものとします。

<!-- numbered-subquestions -->

1. どのような異なる組み合わせが得られますか。
2. 同じ数の組を異なる順番で繰り返し探索する必要がないのはなぜですか。「小さい順」という制約はどのような役割を果たしますか。
3. 現在の経路が `[3]` で、あと 2 必要なとき、次の候補は 3 です。この時点で、この層の残りの全候補を調べずに終えられるのはなぜですか。

??? success "解答例"

    1. 異なる組み合わせは `[2, 3]` と `[5]` です。

    2. この問題では `[2, 3]` と `[3, 2]` を同じ組み合わせとみなし、選んだ順序は答えに含めません。
        経路の数を小さい順に限定すると、探索時に `[3, 2]` のような重複する組み合わせを直接除外できます。

    3. 必要なのはあと 2 ですが、候補の 3 はすでに 2 より大きくなっています。配列は整列済みなので、
        3 より後の候補はさらに大きく、いずれも現在の組み合わせには加えられません。そのため、この層の確認をそこで終えられます。

### 次のクイーンを置ける位置

`4 × 4` の盤面に、行ごとにクイーンを置きます。行と列のインデックスはいずれも 0 から始まります。
すでに `(0, 1)` と `(1, 3)` にクイーンがあり、次のクイーンを第 2 行に置きます。

<!-- numbered-subquestions -->

1. 「同じ列」に当たるために除外されるのは、どの列ですか。
2. 残った列のうち、「同じ対角線」に当たるために除外される位置はどこですか。
3. 第 2 行には、試せる位置がどこに残っていますか。

??? success "解答例"

    1. 第 1 列と第 3 列にはすでにクイーンがあるため、`(2, 1)` と `(2, 3)` は除外されます。

    2. 残った位置のうち、`(2, 2)` は `(1, 3)` と同じ対角線上にあるため、除外されます。
        `(2, 0)` は、既存の二つのクイーンのどちらとも同じ列や対角線上にはありません。

    3. 第 2 行で試せる位置は `(2, 0)` だけです。

        この段階で分かるのは、現在の配置が規則に合っていることだけです。その後に盤面を完成できなければ、前へ戻って、それ以前の別の選択を試す必要があります。

## プログラミング演習

### 重複しない要素の全順列

整数配列 `nums` には少なくとも一つの要素があり、各要素はすべて異なります。
各要素を一回ずつ使って作れる順序をすべて列挙し、それぞれを配列として返してください。
結果内の順列の並び順は問いません。
バックトラッキングを使い、各位置の要素を現在の順列にすでに選んだかどうかを、真偽値の配列で記録してください。

??? tip "解くためのヒント"

    1. 再帰の深さは、順列の何番目の位置を埋めているかを表します
    2. 各層では、まだ使っていない要素だけを試します
    3. 経路の長さが `nums` の長さに達したら、そのコピーを答えに追加します

[LeetCode](https://leetcode.com/problems/permutations/){ .rounded-button .exercise-button target="_blank" rel="noopener noreferrer" }