バックトラッキングアルゴリズム: 組み合わせ問題を解決しましょう!

[[379493]]

バックトラッキングアルゴリズムをほとんど忘れてしまいましたか？組み合わせ問題を解く方法をまだ覚えていますか？ハハハハ

バックトラッキングアルゴリズムは、実際にはブルートフォース検索です。ブルートフォース検索であるなら、なぜバックトラッキングを使用する必要があるのでしょうか。それは、ブルートフォース検索で解決できる問題もあり、これより良い方法がないからです。

2 つの整数 n と k が与えられた場合、1 ... n 内の k 個の数値のすべての可能な組み合わせを返します。

この問題を解決するためにネストされた for ループを使用する場合、n が 100、k が 50 であれば、50 層の for ループが存在することになります。この時点で、単純なブルートフォースは機能しないことがわかります。

ここでバックトラッキングアルゴリズムが登場します。

バックトラックアルゴリズムで再帰を使用して、for ループのカスケードとネストを実行します (k 層の for ループを開くと理解できます)

各再帰で for ループがネストされている場合、再帰によって多層ネストされたループの問題を解決できます。

私の記事「バックトラッキングアルゴリズム: 組み合わせ問題の解決!」でも、バックトラッキング 3 部作について説明しました。この方法によれば、バックトラッキングアルゴリズムは難しくないことがわかります。

問題リンク: https://leetcode-cn.com/problems/combinations/

バックトラッキングアルゴリズムのテンプレートは次のとおりです。

 void バックトラッキング(パラメータ) {
    if (終了条件) {
        結果を保存します。
戻る;
    } 
 
 for (select: 現在のレイヤーセット内の要素 (ツリー内のノードの子の数はセットのサイズです)) {
        処理ノード。
        backtracking(パス, 選択リスト); // 再帰
        バックトラック、処理結果の取り消し
    }
 }