hello-algoで学ぶ全順列問題のバックトラッキング重複選択・等価要素の枝刈りと全言語実装の読み方【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algoこの記事は、オープンソースのアルゴリズム入門書「Hello アルゴリズムhello-algo」の第 13 章「バックトラッキング」の節 全順列問題 を徹底解説する技術ガイドです。順列生成を「選択の積み重ね」として捉えるバックトラッキングの考え方、selectedによる重複選択の枝刈り、duplicatedハッシュ集合による等価要素の枝刈りの設計を、リポジトリに実装された Python・Java・C・Go などのソースコードを交えて学べます。読了後には、重複要素を含む/含まない任意の配列に対して重複のない全順列を列挙するアルゴリズムを、時間計算量・空間計算量の根拠とともに自力で実装できるようになります。全順列問題とは何か全順列問題は、バックトラッキングアルゴリズムの典型的な応用例です。ある集合配列や文字列などが与えられたとき、その要素のあり得るすべての順列を求める問題です。以下に、入力配列とそれに対応するすべての順列の例を示します。入力配列すべての順列$[1]$$[1]$$[1, 2]$$[1, 2], [2, 1]$$[1, 2, 3]$$[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]$互いに異なる $n$ 個の要素に対して順列の総数は $n!$ 通りです。リポジトリではこの問題を、重複要素を含まない「全排列 I」と、重複要素を含む「全排列 II」の 2 段階に分けて解説しています対応ファイルは codes/python/chapter_backtracking/permutations_i.py と codes/python/chapter_backtracking/permutations_ii.py。等しい要素がない場合permutations I!!! question重複要素を含まない整数配列を入力として受け取り、あり得るすべての順列を返します。バックトラッキングの観点順列は選択の結果バックトラッキングアルゴリズムの観点から見ると、順列生成の過程は一連の選択の結果として捉えられます。入力配列が $[1, 2, 3]$ だとすると、最初に $1$ を選び、次に $3$ を選び、最後に $2$ を選べば、順列 $[1, 3, 2]$ が得られます。「戻る」操作は 1 つの選択を取り消し、その後で別の選択を試し続けることを表します。これは同章の バックトラッキングアルゴリズム で述べた「試行attemptと戻るbacktracking」の戦略そのものです。この問題をバックトラッキングのフレームワークに当てはめると、次のようになります。候補集合choices入力配列中のすべての要素。状態state現時点までに選ばれた要素のリスト。制約条件各要素は 1 回しか選べないため、state内の要素はすべて一意でなければなりません。探索過程は下図のような再帰木として展開できます。木の各ノードは現在の状態stateを表し、根ノードから始めて 3 ラウンドの選択を経て葉ノードに到達すると、各葉ノードが 1 つの順列に対応します。重複選択の枝刈り各要素が 1 回しか選ばれないようにするため、ブール配列selectedを導入します。ここでselected[i]はchoices[i]がすでに選ばれているかどうかを表し、これに基づいて次の枝刈りを行います。選択choices[i]を行った後、selected[i]を $\text{True}$ に設定し、その要素が選択済みであることを表します。選択肢リストchoicesを走査するとき、すでに選ばれたノードはすべてスキップします。これが枝刈りです。下図のように、1 回目に 1、2 回目に 3、3 回目に 2 を選ぶ場合、2 回目では要素 1 の分岐を、3 回目では要素 1 と要素 3 の分岐を刈り取る必要があります。この枝刈りにより、何も制約しない場合の探索空間 $O(n^n)$ は $O(n!)$ まで削減されます。つまり「毎ラウンド $n$ 個の選択肢から自由に選ぶ」素朴な深さ優先探索と比較して、順列の構造一度選んだ要素は再選択できないを反映した探索になっている点が重要です。コード実装フレームワークを 1 関数へ展開本書の本文ではバックトラッキングの汎用フレームワークja/docs/chapter_backtracking/backtracking_algorithm.md の「フレームワークコード」節参照を紹介していますが、全順列の実装ではコード全体を短くするため、is_solution・make_choice・undo_choiceなどの各関数を個別に定義せず、backtrack()関数内に展開しています。リポジトリの Python 実装は次のとおりです。def backtrack( state: list[int], choices: list[int], selected: list[bool], res: list[list[int]] ): バックトラッキングアルゴリズム全排列 I # 状態の長さが要素数に等しくなったら解を記録 if len(state) len(choices): res.append(list(state)) return # すべての選択肢を走査 for i, choice in enumerate(choices): # 枝刈り要素の重複選択を禁止 if not selected[i]: # 試行選択を行い、状態を更新 selected[i] True state.append(choice) # 次のラウンドの選択へ backtrack(state, choices, selected, res) # 戻る選択を取り消し、元の状態へ復元 selected[i] False state.pop() def permutations_i(nums: list[int]) - list[list[int]]: 全排列 I res [] backtrack(state[], choicesnums, selected[False] * len(nums), resres) return resコードの要点を整理します。解の判定len(state) len(choices)になった時点で、すべての要素を 1 回ずつ選び終えたことを意味します。このときstateをコピーしてresに追加します。コピーせず同じリストを再利用すると、後続の戻る操作で記録済みの解まで壊れてしまいます。試行と戻るの対称性selected[i] Trueとstate.append(choice)のペアは、必ずselected[i] Falseとstate.pop()のペアで元に戻します。この対称性が崩れると、探索結果に重複や欠落が生じます。複数言語対応同じロジックが各言語で実装されており、言語ごとのメモリ管理・コレクション操作の違いを比較できます。たとえば Java 版 では解の記録にnew ArrayListInteger(state)、Go 版 ではappend([]int{}, *state...)を使い、stateの内容をコピーしてからresへ格納しています。再帰の「戻る」は Java ではstate.remove(state.size() - 1)、Go では*state (*state)[:len(*state)-1]と表現され、いずれも末尾 1 要素の削除に対応します。等しい要素を考慮する場合permutations II!!! question整数配列を入力として受け取り、**配列には重複要素が含まれる場合があります**。重複しない順列をすべて返します。なぜ重複順列が生じるのか入力配列が $[1, 1, 2]$ だと仮定します。2 つの重複する要素 $1$ を区別しやすくするため、2 つ目の $1$ を $\hat{1}$ と記します。このとき、順列 $[1, \hat{1}, 2]$ と $[\hat{1}, 1, 2]$ は「見かけ上」同一の $[1, 1, 2]$ であり、要素の位置だけが入れ替わったものです。したがって、前節のselectedによる枝刈りだけでは、下図のように生成される順列の半分が重複してしまいます。ハッシュ集合による後処理はなぜ不十分か重複を除く最も直接的な方法は、ハッシュ集合setを使って結果の順列をそのまま重複排除することです。たとえば結果を文字列化して set に突っ込む、といった方法です。しかしこのやり方は十分に洗練されていません。なぜなら、重複順列を生成する探索分岐はそもそも不要であり、事前に見つけて枝刈りすべきだからです。後処理方式では不要な再帰呼び出しがすべて実行されてから除外されるため、探索効率の面で損をします。枝刈りを探索中に行えば、アルゴリズム効率をさらに高められます。等しい要素の枝刈り下図を見ると、1 回目のラウンドで $1$ を選ぶことと $\hat{1}$ を選ぶことは等価であり、これら 2 つの選択の下で生成される順列はすべて重複します。したがって $\hat{1}$ は枝刈りすべきです。同様に、1 回目で $2$ を選んだ後では、2 回目のラウンドにおける $1$ と $\hat{1}$ も重複分岐を生むため、2 回目の $\hat{1}$ も枝刈りすべきです。本質的には、各ラウンドの選択において、等しい複数の要素が 1 回しか選ばれないようにすることが目標です。つまりselectedが「要素のインデックス単位」で重複を防ぐのに対し、ここでは「要素の値単位」で重複を防ぐ必要があります。コード実装duplicatedハッシュ集合の導入前問のコードを土台として、各ラウンドの選択でハッシュ集合duplicatedを 1 つ用意し、そのラウンドですでに試した要素の値を記録して、重複要素を枝刈りします。リポジトリの Python 実装は次のとおりです。def backtrack( state: list[int], choices: list[int], selected: list[bool], res: list[list[int]] ): バックトラッキングアルゴリズム全排列 II # 状態の長さが要素数に等しくなったら解を記録 if len(state) len(choices): res.append(list(state)) return # すべての選択肢を走査 duplicated set[int]() for i, choice in enumerate(choices): # 枝刈り要素の重複選択を禁止 かつ 等しい要素の重複選択を禁止 if not selected[i] and choice not in duplicated: # 試行選択を行い、状態を更新 duplicated.add(choice) # 選択した要素の値を記録 selected[i] True state.append(choice) # 次のラウンドの選択へ backtrack(state, choices, selected, res) # 戻る選択を取り消し、元の状態へ復元 selected[i] False state.pop() def permutations_ii(nums: list[int]) - list[list[int]]: 全排列 II res [] backtrack(state[], choicesnums, selected[False] * len(nums), resres) return res前節のコードとの差分は次の 2 点だけです。backtrack()に入った直後に空のduplicated set[int]()を作成する。走査の条件をif not selected[i] and choice not in duplicatedに拡張し、選択時にduplicated.add(choice)で値を記録する。ここで重要なのは、duplicatedをbacktrack()の外や関数冒頭より外側に置かないことです。duplicatedは「1 回の再帰呼び出し内の for ループ」に対してのみ有効な局所変数であり、再帰から戻った後に引き継ぐ必要はありません。むしろ引き継いでしまうと、別のラウンドの選択まで制限してしまい、正しい順列が失われます。なお、Java 版 codes/java/chapter_backtracking/permutations_ii.java ではSetInteger duplicated new HashSetInteger()、C 版 codes/c/chapter_backtracking/permutations_ii.c では配列bool duplicated[MAX_SIZE]をインデックス要素の値で参照する方式で同じ枝刈りを実現しています。C 言語のように要素値が自然数で上限が既知の場合は配列、値域が広い・負数やオブジェクトを含む場合はハッシュ集合が適切です。計算量の解析時間計算量$O(n!n)$要素がすべて互いに異なると仮定すると、$n$ 個の要素には全部で $n!$ 通りの順列階乗があります。結果を記録する際には、長さ $n$ のリストをコピーする必要があり、これに $O(n)$ 時間を要します。したがって時間計算量は $O(n!n)$です。ここで $O(n!)$ は解の個数そのもの、$O(n)$ は解 1 件を記録するためのコピーコストを表します。枝刈りを行わない探索空間 $O(n^n)$ と比べると、$n$ が大きくなるほど差は決定的です。空間計算量$O(n^2)$再帰の最大深さは $n$ であり、$O(n)$ のスタックフレーム空間を使います。selectedは長さ $n$ のブール配列なので $O(n)$ 空間を使用します。duplicatedは再帰の各階層同時刻に存在するbacktrack呼び出しごとに 1 つずつ作られるため、同時に存在するのは最大で $n$ 個、各集合は最大 $O(n)$ サイズとなり、合わせて $O(n^2)$ 空間を要します。したがって全体の空間計算量は $O(n^2)$ です。2 種類の枝刈りの比較selectedとduplicatedはどちらも枝刈りに用いられますが、目的と作用範囲が異なる点に注意してください。混同すると、片方だけを実装して重複が残ったり、逆に正しい順列まで削ってしまったりします。枝刈りデータ構造作用範囲目的重複選択の枝刈りブール配列selected全体で 1 つだけ探索全体すべての再帰呼び出しで共有現在の状態にどの要素が含まれているかを記録し、ある要素がstateに重複して現れるのを防ぐ等しい要素の枝刈りハッシュ集合duplicatedbacktrack呼び出しごとに新規作成各ラウンドの選択1 回のbacktrack内の for ループそのラウンドでどの要素の値がすでに選ばれたかを記録し、等しい要素が 1 回しか選ばれないことを保証する下図は、2 つの枝刈り条件が有効になる範囲を示しています。木の各ノードは 1 つの選択を表し、根ノードから葉ノードまでの経路上の各ノードが 1 つの順列を構成することに注意してください。selectedは「経路」全体を、duplicatedは「1 つのノードから伸びる兄弟分岐」をそれぞれ制御しているイメージです。リポジトリで実際に動かす実行方法hello-algo リポジトリの各コードファイルにはDriver Codemain相当が同梱されています。Python であれば、リポジトリ直下から次のように実行して結果を確認できます出力例は各ファイルの Driver Code に対応。python3 codes/python/chapter_backtracking/permutations_i.py # 入力配列 nums [1, 2, 3] # すべての排列 res [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] python3 codes/python/chapter_backtracking/permutations_ii.py # 入力配列 nums [1, 2, 2] # すべての排列 res [[1, 2, 2], [2, 1, 2], [2, 2, 1]]注意点として、Driver Code の入力は本文の説明$[1, 1, 2]$とは異なりnums [1, 2, 2]を使っていますが、これは同じ「重複要素を持つ 3 要素配列」の例であり、出力が $3 3! / 2!$ 通りになる点は同じです。テストをまとめて実行したい場合は codes/python/test_all.py が参考になります。各言語の対応ファイル一覧この節の 2 つの解法は、リポジトリの主要言語すべてに同内容で実装されています。型の強い言語と弱い言語、コレクション標準ライブラリの差異を横断的に読むことで、バックトラッキングの骨格が言語に依存しないことを実感できます。Pythonpermutations_i.py / permutations_ii.pyJavapermutations_i.java / permutations_ii.javaCpermutations_i.cpp / permutations_ii.cppCpermutations_i.c / permutations_ii.cGopermutations_i.go / permutations_ii.goTypeScriptpermutations_i.ts / permutations_ii.tsそのほか JavaScript・C#・Swift・Rust・Kotlin・Dart・Ruby も同章の chapter_backtracking ディレクトリ 内に揃っています。日本語版ドキュメントは ja/docs/chapter_backtracking/permutations_problem.md にあり、図版は permutations_problem.assets に格納されています。まとめ枝刈りの設計がバックトラッキングの効率を決める本節で学んだ要点を整理します。全順列問題はバックトラッキングの代表例であり、状態state・候補choices・制約要素の一意性という 3 要素で定式化できます。重複要素がない場合はselectedの 1 本の枝刈りで十分です。これにより探索空間は $O(n^n)$ から $O(n!)$ へ削減されます。重複要素がある場合は、結果を後から重複排除するのではなく、duplicatedハッシュ集合で探索中に等価分岐を刈るのが本質的です。時間計算量は $O(n!n)$、空間計算量は $O(n^2)$ となります。selected経路全体を制御とduplicated1 ラウンド内の兄弟分岐を制御は作用範囲が異なるため、役割を区別して実装することが重要です。この「試行 → 条件判定 → 戻る」の骨格は、同章の 部分和問題値の重複を許す組合せ列挙や n クイーン問題対角線・行・列の制約へもそのまま応用できます。順列・組合せ・制約充足という 3 つの典型問題を通じて枝刈りの設計感覚を磨くことで、実務の探索問題にも応用できる汎用的なスキルが身につきます。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 hello-algoで学ぶ全順列問題のバックトラッキング：重複選択・等価要素の枝刈りと全言語実装の読み方
hello-algoで学ぶ全順列問題のバックトラッキング重複選択・等価要素の枝刈りと全言語実装の読み方【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algoこの記事は、オープンソースのアルゴリズム入門書「Hello アルゴリズムhello-algo」の第 13 章「バックトラッキング」の節 全順列問題 を徹底解説する技術ガイドです。順列生成を「選択の積み重ね」として捉えるバックトラッキングの考え方、selectedによる重複選択の枝刈り、duplicatedハッシュ集合による等価要素の枝刈りの設計を、リポジトリに実装された Python・Java・C・Go などのソースコードを交えて学べます。読了後には、重複要素を含む/含まない任意の配列に対して重複のない全順列を列挙するアルゴリズムを、時間計算量・空間計算量の根拠とともに自力で実装できるようになります。全順列問題とは何か全順列問題は、バックトラッキングアルゴリズムの典型的な応用例です。ある集合配列や文字列などが与えられたとき、その要素のあり得るすべての順列を求める問題です。以下に、入力配列とそれに対応するすべての順列の例を示します。入力配列すべての順列$[1]$$[1]$$[1, 2]$$[1, 2], [2, 1]$$[1, 2, 3]$$[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]$互いに異なる $n$ 個の要素に対して順列の総数は $n!$ 通りです。リポジトリではこの問題を、重複要素を含まない「全排列 I」と、重複要素を含む「全排列 II」の 2 段階に分けて解説しています対応ファイルは codes/python/chapter_backtracking/permutations_i.py と codes/python/chapter_backtracking/permutations_ii.py。等しい要素がない場合permutations I!!! question重複要素を含まない整数配列を入力として受け取り、あり得るすべての順列を返します。バックトラッキングの観点順列は選択の結果バックトラッキングアルゴリズムの観点から見ると、順列生成の過程は一連の選択の結果として捉えられます。入力配列が $[1, 2, 3]$ だとすると、最初に $1$ を選び、次に $3$ を選び、最後に $2$ を選べば、順列 $[1, 3, 2]$ が得られます。「戻る」操作は 1 つの選択を取り消し、その後で別の選択を試し続けることを表します。これは同章の バックトラッキングアルゴリズム で述べた「試行attemptと戻るbacktracking」の戦略そのものです。この問題をバックトラッキングのフレームワークに当てはめると、次のようになります。候補集合choices入力配列中のすべての要素。状態state現時点までに選ばれた要素のリスト。制約条件各要素は 1 回しか選べないため、state内の要素はすべて一意でなければなりません。探索過程は下図のような再帰木として展開できます。木の各ノードは現在の状態stateを表し、根ノードから始めて 3 ラウンドの選択を経て葉ノードに到達すると、各葉ノードが 1 つの順列に対応します。重複選択の枝刈り各要素が 1 回しか選ばれないようにするため、ブール配列selectedを導入します。ここでselected[i]はchoices[i]がすでに選ばれているかどうかを表し、これに基づいて次の枝刈りを行います。選択choices[i]を行った後、selected[i]を $\text{True}$ に設定し、その要素が選択済みであることを表します。選択肢リストchoicesを走査するとき、すでに選ばれたノードはすべてスキップします。これが枝刈りです。下図のように、1 回目に 1、2 回目に 3、3 回目に 2 を選ぶ場合、2 回目では要素 1 の分岐を、3 回目では要素 1 と要素 3 の分岐を刈り取る必要があります。この枝刈りにより、何も制約しない場合の探索空間 $O(n^n)$ は $O(n!)$ まで削減されます。つまり「毎ラウンド $n$ 個の選択肢から自由に選ぶ」素朴な深さ優先探索と比較して、順列の構造一度選んだ要素は再選択できないを反映した探索になっている点が重要です。コード実装フレームワークを 1 関数へ展開本書の本文ではバックトラッキングの汎用フレームワークja/docs/chapter_backtracking/backtracking_algorithm.md の「フレームワークコード」節参照を紹介していますが、全順列の実装ではコード全体を短くするため、is_solution・make_choice・undo_choiceなどの各関数を個別に定義せず、backtrack()関数内に展開しています。リポジトリの Python 実装は次のとおりです。def backtrack( state: list[int], choices: list[int], selected: list[bool], res: list[list[int]] ): バックトラッキングアルゴリズム全排列 I # 状態の長さが要素数に等しくなったら解を記録 if len(state) len(choices): res.append(list(state)) return # すべての選択肢を走査 for i, choice in enumerate(choices): # 枝刈り要素の重複選択を禁止 if not selected[i]: # 試行選択を行い、状態を更新 selected[i] True state.append(choice) # 次のラウンドの選択へ backtrack(state, choices, selected, res) # 戻る選択を取り消し、元の状態へ復元 selected[i] False state.pop() def permutations_i(nums: list[int]) - list[list[int]]: 全排列 I res [] backtrack(state[], choicesnums, selected[False] * len(nums), resres) return resコードの要点を整理します。解の判定len(state) len(choices)になった時点で、すべての要素を 1 回ずつ選び終えたことを意味します。このときstateをコピーしてresに追加します。コピーせず同じリストを再利用すると、後続の戻る操作で記録済みの解まで壊れてしまいます。試行と戻るの対称性selected[i] Trueとstate.append(choice)のペアは、必ずselected[i] Falseとstate.pop()のペアで元に戻します。この対称性が崩れると、探索結果に重複や欠落が生じます。複数言語対応同じロジックが各言語で実装されており、言語ごとのメモリ管理・コレクション操作の違いを比較できます。たとえば Java 版 では解の記録にnew ArrayListInteger(state)、Go 版 ではappend([]int{}, *state...)を使い、stateの内容をコピーしてからresへ格納しています。再帰の「戻る」は Java ではstate.remove(state.size() - 1)、Go では*state (*state)[:len(*state)-1]と表現され、いずれも末尾 1 要素の削除に対応します。等しい要素を考慮する場合permutations II!!! question整数配列を入力として受け取り、**配列には重複要素が含まれる場合があります**。重複しない順列をすべて返します。なぜ重複順列が生じるのか入力配列が $[1, 1, 2]$ だと仮定します。2 つの重複する要素 $1$ を区別しやすくするため、2 つ目の $1$ を $\hat{1}$ と記します。このとき、順列 $[1, \hat{1}, 2]$ と $[\hat{1}, 1, 2]$ は「見かけ上」同一の $[1, 1, 2]$ であり、要素の位置だけが入れ替わったものです。したがって、前節のselectedによる枝刈りだけでは、下図のように生成される順列の半分が重複してしまいます。ハッシュ集合による後処理はなぜ不十分か重複を除く最も直接的な方法は、ハッシュ集合setを使って結果の順列をそのまま重複排除することです。たとえば結果を文字列化して set に突っ込む、といった方法です。しかしこのやり方は十分に洗練されていません。なぜなら、重複順列を生成する探索分岐はそもそも不要であり、事前に見つけて枝刈りすべきだからです。後処理方式では不要な再帰呼び出しがすべて実行されてから除外されるため、探索効率の面で損をします。枝刈りを探索中に行えば、アルゴリズム効率をさらに高められます。等しい要素の枝刈り下図を見ると、1 回目のラウンドで $1$ を選ぶことと $\hat{1}$ を選ぶことは等価であり、これら 2 つの選択の下で生成される順列はすべて重複します。したがって $\hat{1}$ は枝刈りすべきです。同様に、1 回目で $2$ を選んだ後では、2 回目のラウンドにおける $1$ と $\hat{1}$ も重複分岐を生むため、2 回目の $\hat{1}$ も枝刈りすべきです。本質的には、各ラウンドの選択において、等しい複数の要素が 1 回しか選ばれないようにすることが目標です。つまりselectedが「要素のインデックス単位」で重複を防ぐのに対し、ここでは「要素の値単位」で重複を防ぐ必要があります。コード実装duplicatedハッシュ集合の導入前問のコードを土台として、各ラウンドの選択でハッシュ集合duplicatedを 1 つ用意し、そのラウンドですでに試した要素の値を記録して、重複要素を枝刈りします。リポジトリの Python 実装は次のとおりです。def backtrack( state: list[int], choices: list[int], selected: list[bool], res: list[list[int]] ): バックトラッキングアルゴリズム全排列 II # 状態の長さが要素数に等しくなったら解を記録 if len(state) len(choices): res.append(list(state)) return # すべての選択肢を走査 duplicated set[int]() for i, choice in enumerate(choices): # 枝刈り要素の重複選択を禁止 かつ 等しい要素の重複選択を禁止 if not selected[i] and choice not in duplicated: # 試行選択を行い、状態を更新 duplicated.add(choice) # 選択した要素の値を記録 selected[i] True state.append(choice) # 次のラウンドの選択へ backtrack(state, choices, selected, res) # 戻る選択を取り消し、元の状態へ復元 selected[i] False state.pop() def permutations_ii(nums: list[int]) - list[list[int]]: 全排列 II res [] backtrack(state[], choicesnums, selected[False] * len(nums), resres) return res前節のコードとの差分は次の 2 点だけです。backtrack()に入った直後に空のduplicated set[int]()を作成する。走査の条件をif not selected[i] and choice not in duplicatedに拡張し、選択時にduplicated.add(choice)で値を記録する。ここで重要なのは、duplicatedをbacktrack()の外や関数冒頭より外側に置かないことです。duplicatedは「1 回の再帰呼び出し内の for ループ」に対してのみ有効な局所変数であり、再帰から戻った後に引き継ぐ必要はありません。むしろ引き継いでしまうと、別のラウンドの選択まで制限してしまい、正しい順列が失われます。なお、Java 版 codes/java/chapter_backtracking/permutations_ii.java ではSetInteger duplicated new HashSetInteger()、C 版 codes/c/chapter_backtracking/permutations_ii.c では配列bool duplicated[MAX_SIZE]をインデックス要素の値で参照する方式で同じ枝刈りを実現しています。C 言語のように要素値が自然数で上限が既知の場合は配列、値域が広い・負数やオブジェクトを含む場合はハッシュ集合が適切です。計算量の解析時間計算量$O(n!n)$要素がすべて互いに異なると仮定すると、$n$ 個の要素には全部で $n!$ 通りの順列階乗があります。結果を記録する際には、長さ $n$ のリストをコピーする必要があり、これに $O(n)$ 時間を要します。したがって時間計算量は $O(n!n)$です。ここで $O(n!)$ は解の個数そのもの、$O(n)$ は解 1 件を記録するためのコピーコストを表します。枝刈りを行わない探索空間 $O(n^n)$ と比べると、$n$ が大きくなるほど差は決定的です。空間計算量$O(n^2)$再帰の最大深さは $n$ であり、$O(n)$ のスタックフレーム空間を使います。selectedは長さ $n$ のブール配列なので $O(n)$ 空間を使用します。duplicatedは再帰の各階層同時刻に存在するbacktrack呼び出しごとに 1 つずつ作られるため、同時に存在するのは最大で $n$ 個、各集合は最大 $O(n)$ サイズとなり、合わせて $O(n^2)$ 空間を要します。したがって全体の空間計算量は $O(n^2)$ です。2 種類の枝刈りの比較selectedとduplicatedはどちらも枝刈りに用いられますが、目的と作用範囲が異なる点に注意してください。混同すると、片方だけを実装して重複が残ったり、逆に正しい順列まで削ってしまったりします。枝刈りデータ構造作用範囲目的重複選択の枝刈りブール配列selected全体で 1 つだけ探索全体すべての再帰呼び出しで共有現在の状態にどの要素が含まれているかを記録し、ある要素がstateに重複して現れるのを防ぐ等しい要素の枝刈りハッシュ集合duplicatedbacktrack呼び出しごとに新規作成各ラウンドの選択1 回のbacktrack内の for ループそのラウンドでどの要素の値がすでに選ばれたかを記録し、等しい要素が 1 回しか選ばれないことを保証する下図は、2 つの枝刈り条件が有効になる範囲を示しています。木の各ノードは 1 つの選択を表し、根ノードから葉ノードまでの経路上の各ノードが 1 つの順列を構成することに注意してください。selectedは「経路」全体を、duplicatedは「1 つのノードから伸びる兄弟分岐」をそれぞれ制御しているイメージです。リポジトリで実際に動かす実行方法hello-algo リポジトリの各コードファイルにはDriver Codemain相当が同梱されています。Python であれば、リポジトリ直下から次のように実行して結果を確認できます出力例は各ファイルの Driver Code に対応。python3 codes/python/chapter_backtracking/permutations_i.py # 入力配列 nums [1, 2, 3] # すべての排列 res [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] python3 codes/python/chapter_backtracking/permutations_ii.py # 入力配列 nums [1, 2, 2] # すべての排列 res [[1, 2, 2], [2, 1, 2], [2, 2, 1]]注意点として、Driver Code の入力は本文の説明$[1, 1, 2]$とは異なりnums [1, 2, 2]を使っていますが、これは同じ「重複要素を持つ 3 要素配列」の例であり、出力が $3 3! / 2!$ 通りになる点は同じです。テストをまとめて実行したい場合は codes/python/test_all.py が参考になります。各言語の対応ファイル一覧この節の 2 つの解法は、リポジトリの主要言語すべてに同内容で実装されています。型の強い言語と弱い言語、コレクション標準ライブラリの差異を横断的に読むことで、バックトラッキングの骨格が言語に依存しないことを実感できます。Pythonpermutations_i.py / permutations_ii.pyJavapermutations_i.java / permutations_ii.javaCpermutations_i.cpp / permutations_ii.cppCpermutations_i.c / permutations_ii.cGopermutations_i.go / permutations_ii.goTypeScriptpermutations_i.ts / permutations_ii.tsそのほか JavaScript・C#・Swift・Rust・Kotlin・Dart・Ruby も同章の chapter_backtracking ディレクトリ 内に揃っています。日本語版ドキュメントは ja/docs/chapter_backtracking/permutations_problem.md にあり、図版は permutations_problem.assets に格納されています。まとめ枝刈りの設計がバックトラッキングの効率を決める本節で学んだ要点を整理します。全順列問題はバックトラッキングの代表例であり、状態state・候補choices・制約要素の一意性という 3 要素で定式化できます。重複要素がない場合はselectedの 1 本の枝刈りで十分です。これにより探索空間は $O(n^n)$ から $O(n!)$ へ削減されます。重複要素がある場合は、結果を後から重複排除するのではなく、duplicatedハッシュ集合で探索中に等価分岐を刈るのが本質的です。時間計算量は $O(n!n)$、空間計算量は $O(n^2)$ となります。selected経路全体を制御とduplicated1 ラウンド内の兄弟分岐を制御は作用範囲が異なるため、役割を区別して実装することが重要です。この「試行 → 条件判定 → 戻る」の骨格は、同章の 部分和問題値の重複を許す組合せ列挙や n クイーン問題対角線・行・列の制約へもそのまま応用できます。順列・組合せ・制約充足という 3 つの典型問題を通じて枝刈りの設計感覚を磨くことで、実務の探索問題にも応用できる汎用的なスキルが身につきます。【免费下载链接】hello-algo《Hello 算法》动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語提供 Python, Java, C, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考