バックトラッキングへの究極のガイド

バックトラッキングは、すべての可能な解決策を調査することによって問題を解決するためのテクニックです.
バックトラッキングの問題は、組み合わせや置換を見つけることを求める.これらのPS＆Csは、それから特定の条件または最小の/最大の論理に対してマッチされます.以下に例を示します:

数の配列を与えられて、与えられた数に加える数のすべての可能な組合せを見つけてください.

は、はっきりした整数のコレクションを与えられます.

この記事では、これらの2つの問題を解決するためにバックトラッキングを使用します.そうすることで、我々は詳細にプロセスの各ステップを通過します.
我々はまた、これらの問題のいくつかの重要な変化を見て、どのように解決するために解決策を変更します.
つまり、以下の手順でバックトラッキングをドリルダウンできます.

州から始まります.

現在の状態が解決の場合は、現在の状態を結果に追加します.

がなければ、現在の状態から可能な動きを試してみてください.

私たちはすべての可能な動き、前の状態へのバックトラックを試みた.

は解決策が見つかるまで、上記の手順を繰り返します.

問題1：組み合わせ

以下の問題を解決しましょう.
は、明確な正の数のリストを与えられた、特定の数に追加するすべての組み合わせを見つける.
入力[ 1 , 2 , 3 , 4 ] ,ターゲット= 5
出力:[[ 2 , 3 ], [ 1 , 4 ] ]
この問題を解決するためにバックトラッキング手法を使いましょう.
免責事項:この問題を解決するために多くの方法があります.私は説明するのが簡単である方法を選びました.私は、コードを単純にしておくどんな巧妙なトリックも残しました.
プログラミング例はJavaにありますが、特別なデータ構造を使用しません.

初期状態

初期状態は空リストです.我々はこの状態から始めて、それに数字を加えてみるつもりです.
以下の通りです.

現在の状態または使用される番号のリスト.

リスト内の数字の合計.

public List<List<Integer>> combinationSum(int[] nums, int target) {
    // will store the final result
    List<List<Integer>> res = new ArrayList<>(); 

    // keeps track of the current state
    List<Integer> current = new ArrayList<>();

    // call the helper function which does the processing 
    // first 0 is the sum of the numbers in the current state
    // second 0 is the index to start from
    backtrack(nums, target, 0, 0, current, res);
    return res;
}

現在の状態が解決かどうかチェックする

現在の状態が解決策かどうかチェックする必要があります.
そうするためには、現在の状態の数の合計がターゲットに等しいかどうかを確認する必要があります.
yesの場合、現在の状態を最終結果に追加します.

void backtrack(int[] nums, int target, int sum, int index, List<Integer> current, List<List<Integer>> res) {
    // if the sum of the numbers in the current state is equal to the target,
    // then we have found a solution
    if (target == sum) {
        // copy the content of the current state to a new list and save to result
        res.add(new ArrayList<>(current));
        return;
    } else if(sum > target) {
        // short circuit, if the sum of the numbers in the current state is greater than the target,
        return;
    }

    // to be continued...
}

可能な動きとバックトラックの各をお試しください

現在の状態が解決されていない場合は、それぞれの動きを試す必要があります.
可能な動きは、インデックスの上または後に来るnums配列のすべての数字です.
これを3段階に分けることができます.

現在のリストに番号を追加して、次の状態にします.

バックトラック関数を呼び出して、次の状態が解決策かどうかを確認します.インデックスとsumを更新します.

前の状態に戻るには、現在のリストから番号を削除します.次の反復は、次の番号を試してください.

void backtrack(int[] nums, int target, int sum, int index, List<Integer> current, List<List<Integer>> res) {
    // checking for solution - omitted

    for (int i = index; i < nums.length; i++) {
        // add the current number to the current state
        current.add(nums[i]);

        // call the helper function to try the next state - Current sum is updated and index is increased to the next number
        backtrack(nums, target, sum + nums[i], i + 1, current, res);

        // remove the current number from the current state
        current.remove(current.size() - 1);
    }
}

バリエーション1：数字は明確ではありません

我々は同じソリューションを実行した場合、しかし、数字が異なっていないと、我々は重複した結果を得るだろう.
例えば、[ 1 , 2 , 2 , 3 , 4 ]は[ [ 1 , 2 , 2 ] , [ 1 , 4 ] , [ 2 , 3 ] , [ 2 , 3 ] ]を返す

ソリューション1 :ストア結果の設定

この問題を解決する最も簡単な方法は、最終的な結果を追跡し、最後にリストをセットに変換するためのセットを使用することです.
これは正しい解決につながるが、これはいくつかの不必要な作業を行うに行われます.結果に含まれていない場合でも、重複結果はまだ計算されています.

public List<List<Integer>> combinationSum(int[] nums, int target) {
    // will store the temporary result
    Set<List<Integer>> res = new HashSet<>(); 

    List<Integer> current = new ArrayList<>();
    backtrack(nums, target, 0, 0, current, res);

    // convert the set to a list
    return new ArrayList<>(res);
}

解決2：重複移動を避ける

より良い方法は、次の状態を形成しながら重複する動きを除外することです.
我々の現在の状態が[ 1 ]であると仮定してください
残りの数値をループすると以下のような状態になります.
［1,2］,［1,2］,［1,3］,［1,4］
重複移動を避けるために、私たちがする必要があるのは、数が2回処理されているかどうかをチェックすることです.
我々はセットで処理された数字を入れて、数がセットにすでにあるならば、我々はそれをスキップすることができます.

void backtrack(int[] nums, int target, int sum, int index, List<Integer> current, Set<List<Integer>> res) {
    // checking for solution - omitted

    Set<Integer> set = new HashSet<>();
    for (int i = index; i < nums.length; i++) {
        // if the current number is already in the set, skip it
        if (set.contains(nums[i])) {
            continue;
        }

        //processing - call and backtrack - omitted

        // add the current number to the set
        set.add(nums[i]);
    }
}

結果の順序が重要でない場合は、さらに設定を削除することができます.
以下の手順を示します:

すべての複製が一緒に来るように、初期の配列をソートします.

セットを使用する代わりに、以前の数と比較し、同じならばスキップします.

配列numsがソートされると、以下のコードはset - logicを置き換えることができます.

void backtrack(int[] nums, int target, int sum, int index, List<Integer> current, List<List<Integer>> res) {
    // checking for solution - omitted
    for (int i = index; i < nums.length; i++) {
        // if the current number is already in the set, skip it
        if (i > index && nums[i] == nums[i - 1]) {
            continue;
        }
        //processing - call and backtrack - omitted
    }
}

バリエーション2：数は何度も使用することができます

私たちがそれぞれの数を何度も使うことができれば、結果は変わります.
例えば、5の目標和のために[ 1 , 2 , 3 , 4 ]は[ 1 , 1 , 1 , 1 , 1 ], [ 1 , 1 , 1 , 2 ], [ 1 , 1 , 3 ], [ 1 , 2 , 2 ], [ 1 , 4 ], [ 2 , 3 ]を返す
これは、我々の再帰的な呼び出しの非常に小さな変化につながります.
同じ数が再びソリューションで使用できるため、再帰関数を呼び出しながらインデックスをインクリメントしません.

void backtrack(int[] nums, int target, int sum, int index, List<Integer> current, List<List<Integer>> res) {
    // checking for solution - omitted

    for (int i = index; i < nums.length; i++) {
        current.add(nums[i]);

        // sum is updated but index is not incremented
        backtrack(nums, target, sum + nums[i], i, current, res);

        current.remove(current.size() - 1);
    }
}

問題2 :置換

以下の問題を解決しましょう.
明確な整数のコレクションを与えられた場合、それらのすべての置換を返します.
入力:[ 1 , 2 , 3 ]
出力:
[ 1 , 2 , 3 ], [ 1 , 3 , 2 ], [ 2 , 1 , 3 ], [ 2 , 3 , 1 ], [ 3 , 1 , 2 ], [ 3 , 2 , 1 ]
私たちの直感がはっきりしたら、これは単純になります.置換を行うには、2つの重要な原則があります.

すべての要素を含みます-これは停止条件を形成します.

要素を1回以上含めることができます.これは、どんな状態でも、我々の可能な動きは、我々が以前に含めなかった要素だけを含むことを意味します.

我々は、組み合わせの問題に使用される同様のアプローチを使用し、上記の2点を組み込むでしょう.

停止条件

停止条件は、すべての要素が含まれていることです.

void backtrack(int[] nums,  Set<Integer> current, List<List<Integer>> res) {
    if(current.size() == nums.length) {
        res.add(new ArrayList<>(current));
        return;
    }

    // otherwise process
}

可能な動き

可能な移動は、現在の状態に含まれていない要素です.
これを2つのステップに分けることができます.

現在の状態で使用されている番号を格納します.簡単な言葉で、現在の状態のセットを維持します.

各移動後のすべての番号をチェックします.現在の数値の後のすべての数字の可能性をチェックしたいので、前にインデックス変数を維持する必要はありません.

void backtrack(int[] nums,  Set<Integer> current, List<List<Integer>> res) {
    // stopping condition - omitted

    // starting from the first element always
    for(int i = 0; i < nums.length; i++) {

        // if the current number is already in the set, skip it
        if (current.contains(nums[i])) {
            continue;
        }
        current.add(nums[i]);
        backtrack(nums, current, res);
        current.remove(current.size() - 1);        
    }
}

セットがLinkedashSetである必要があることに注意してください.これは、要素の順序を維持する必要があるためです.それがそうでないならば、すべては離れます(少なくともJavaで).あなたが順序反復を提供するあなたの言語でセットされた選択肢を持たないならば、単にリストを使用してください.含まれている演算は、時間の複雑さ(後述)の順序とは異なりません.

変化：数は異なりません

いくつかの数が異なっていないなら、上記の解決は可能な順列を見つけることができません.
これは、一度数が使用されているため、そのチェックはtrueを返し、再び使用できません.
現在のセットは、元の配列の長さを持つことはありません、我々は永遠にバックトラックの機能で立ち往生されます.

インデックスのセット

解決策は簡単です.値のセットを維持する代わりに、我々は一連のインデックスを維持することができます.インデックスは常に一意です.
現在の状態に含まれる一連のインデックスを維持するには、Boolean配列を使用できます.
boolean配列は、現在のset/listと同じように更新されます.

void backtrack(int[] nums,  Set<Integer> current, List<List<Integer>> res, boolean[] used) {
        // stopping condition - omitted

        for(int i = 0; i < nums.length; i++) {
            // if the current number is already in the set, skip it
            if (used[i]) {
                continue;
            }
            // add to boolean array as well as current set
            used[i] = true;
            current.add(nums[i]);

            backtrack(nums, current, res, used);

            // remove from boolean array as well as current set
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }

時間複雑度

これらのバックトラッキングアルゴリズムの各々の理論的時間複雑度は、O(n!)であるnは入力配列の要素数です.
これは次の直感で計算できます.
あらゆるステップで

、我々は選択から選択する必要があります.

すべての選択肢を作った後、私たちはそれぞれのN - 1の選択肢を作らなければならない.

など.

ステップ数= NX ( n - 1 ) x ( n - 2 ) x .X 1 = N !
これは全てのバックトラッキングアルゴリズムがO ( n !)であることを意味しません.それはすべての各ステップで選択の数に依存します.
読書ありがとう.このポストカバーの問題と変化は、バックトラッキング技術の最も一般的な変化.
あなたが役に立つこの記事を見つけた場合は、必要な人々と共有することを忘れないでください-どんな方法で可能です.
あなたは私と接続する場合は、上または私を見つけることができます.