順列

交換型バックトラッキングは一位置ずつ固定します。残りの値を start へ交換し、再帰後に同じ交換を繰り返して、呼び出し元の配列を戻します。異なる n 値なら n! 順序を出力します。

各呼び出しは配列を借り、後方を並べ替えても返す時は元通りにします。それで次の選択に状態を作り直さず進めます。作業配列を変更でき、全順序が必要な時に適します。共有変更が困難なら path + remaining の形もあり、より多くの一時配列を使います。

再帰の選択

nums = [1, 2, 3] で backtrack(0) を呼びます。位置 0 の選択は次です。

1. 自己交換で 1 を残し、[2, 3] を処理する。
2. 2 を交換で入れ、[1, 3] を処理する。
3. 3 を入れ、[2, 1] を処理する。

最初の backtrack(1) は 2 を残し、次は 3 一つなので [1, 2, 3] を出します。戻してから位置 1 に 3 を入れ、[1, 3, 2] を出します。

根の第二選択より前に、内側の交換と根の自己交換がすべて戻り、配列は [1, 2, 3] です。画面は保存した呼び出し元のスナップショットとの一致を示してから、位置 0 と 1 を交換します。

表示トークンは同値でも安定した識別子を持ち、元位置を追えます。コード自体は通常の数値配列です。

葉が n! になる理由

深さ 0 は n 選択、次は n−1、最後は一つです。

n * (n - 1) * ... * 1 = n!

三要素なら 3 * 2 * 1 = 6。各因子が一深度の位置選択で、完成経路が一基底ケースへ到達します。

基底では配列を result へコピーします。元の nums はその後も変わります。同じ参照を追加すれば全結果が一オブジェクトを指し、最後はすべて復元後の順序になります。

復元の不変条件

backtrack(start) の各ループ開始前に、nums はこの呼び出しが受け取った順序と完全に一致しなければなりません。

順方向の交換が子状態を作ります。子は多数の交換をしても、自分の入口状態へ戻してから返ります。現在の逆交換が、さらに現在の入口状態を戻します。

一行が全子孫の操作を直接取り消すのではありません。各子孫が同じ契約を果たしているから一行で済みます。逆交換を外すと、異なる値が三つ以上あれば重複する順列と欠ける順列が生じます。[1, 2] が正しく見えるのは偶然です。最初の部分木は自己交換しかせず、二つ目の根の選択も [1, 2] から始まります。再帰だけで復元がなければ完全なバックトラッキングではありません。

復元しない場合

No restore は二回目の交換だけを除きます。最初の根部分木が [1, 2, 3] でなく [1, 3, 2] を返し、次の兄弟が誤った入口から始まります。

六葉には達しても、値の列は [1, 2, 3]、[1, 3, 2]、[3, 1, 2]、[3, 2, 1] の四種類です。最初の二つが二回ずつ出て、[2, 1, 3] と [2, 3, 1] が欠けます。六基底訪問は六順列の保証ではありません。

生成をステップで追う

既定 [1, 2, 3] の復元ありの全実行です。

1. 根で 1 を選び自己交換、深さ 1 で 2、深さ 2 で 3 を保ち、[1, 2, 3] をコピー。
2. 内側の自己交換を戻し、深さ 1 で 3 を選び [1, 3, 2]。全交換を戻して根は [1, 2, 3]。
3. 根で 2 を選び位置 0、1 を交換、[2, 1, 3]。内側で 1、3 を選び [2, 1, 3] と [2, 3, 1]。
4. 戻して [1, 2, 3]。根で 3 を選び位置 0、2 を交換、[3, 2, 1]。
5. 深さ 1 で 2 を保ち、次に位置 1、2 を交換して、[3, 2, 1] と [3, 1, 2]。
6. 最後の逆交換で [1, 2, 3] に復元し、六つの独立コピーを返す。

結果欄は最初に選んだトークンの識別子で分け、各群に (n - 1)! 個を置きます。スタックは現在の因子を示します。i === start の自己交換も実際のステップで、各深度を同じ規則に保ちます。

同値と一意な順列

このアルゴリズムは位置を区別します。[1, 1, 2] の二つの 1 は別の出所なので 3! = 6 の位置葉です。しかし値は [1, 1, 2]、[1, 2, 1]、[2, 1, 1] の三種類で各二回です。

重複プリセットは六追加を残し、再出現を前の一致へ結びます。隠れて除去しません。一意の順列が必要なら、各深度のループで同値選択を飛ばし、局所の used 集合などを使います。生成後の集合化は重複の階乗仕事をすでに支払っています。

時間・空間計算量

その場交換は探索状態を小さくしますが、出力費用は消せません。画面は四要素までです。四要素の 24 葉でも説明の速度で約 2 分 35 秒。n = 12 なら 12! = 479,001,600 葉で、それぞれ十二値のコピーが必要です。

小さい全順列は総当たりの巡回路、文字配置、短い日程に使えます。n が小さいか、制約で多くの枝を切れるかを確認してください。どちらもなければ全列挙は実用的でない場合が多くなります。

境界ケース

• 一要素は一順列。自己交換、コピー、復元を行う。
• 空配列は一つの空順列と定義することが多い。画面は一〜四要素だが、実装は空も扱える。
• 負数や同値も内容として有効。走査順は位置で決まる。
• ループを逆順にしても異なる値の結果集合は同じで、出力順だけ変わる。
• Python は nums.copy()、JavaScript は [...nums] で保存する。

よくある間違い

• 逆交換を忘れる。 次の兄弟が変更済み配列を受けます。異なる値が三つ以上あれば、重複する順列と欠ける順列が生じます。
• 可変配列をそのまま追加する。 全結果が同じ物を指し、後の交換が過去の答えを変えます。
• 再帰で i を進める。 呼ぶのは backtrack(start + 1)。候補カーソルと固定済み長は別です。
• グローバル used で重複を除く。 一枝で使っても兄弟では再利用できます。除外は一深度に限定します。
• 各葉を一意の値列と呼ぶ。 n! は位置選択で、値が異なる時だけ一意列数と一致します。

どの状態表現でも、選択、再帰、呼び出し元の状態の復元という契約を保ちます。