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

[[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(パス, 選択リスト); // 再帰
        バックトラック、処理結果の取り消し
    }
 }

この記事はWeChatの公開アカウント「Code Thoughts」から転載したもので、以下のQRコードからフォローできます。この記事を転載する場合は、Code Thoughts の公開アカウントにご連絡ください。