バックトラッキングアルゴリズムを使用して PHP のサブセット問題を解決する方法

バックトラッキング アルゴリズムは、実際には列挙に似た検索試行プロセスです。主に、検索試行プロセス中に問題の解決策を検索します。解決条件が満たされなくなったことが判明すると、「バックトラック」して、戻って他のパスを試してください。バックトラッキング法とは、最適化条件に従って目的を達成するために前方へ探索する最適化探索法です。

探索の特定のステップに到達し、元の選択が最適ではない、または目標を達成できないことがわかった場合、一歩下がって選択し直すことになります。うまくいかなかったら戻ってやり直すという後戻り手法であり、後戻り条件を満たすある状態にある点を「後戻りポイント」といいます。多くの複雑で大規模な問題では、「普遍的な問題解決法」として知られるバックトラッキング法を使用できます。

サブセット

重複要素のない整数配列 num のセットを指定すると、配列の可能なすべてのサブセット (べき集合) を返します。

注: ソリューション セットには、繰り返しのサブセットを含めることはできません。

例:

输入: nums = [1,2,3]
输出:[  [3],  
[1],  
[2],  
[1,2,3], 
[1,3],  
[2,3], 
[1,2],  
[]]

問題解決のアイデア 1

バックトラッキング アルゴリズム グループ消去順列/組み合わせへの直接参照サブセット問題

コード

class Solution {
    public $result = [];
    /** 
    * @param Integer[] $nums 
    * @return Integer[][] 
    */
    function subsets($nums) {
       $this->dfs(0, $nums, []);
       return $this->result;
    }
    // 递归部分 
    function dfs($start, $nums, $array){
        $this->result[] = $array;
        for ($i = $start; $i < count($nums); $i++) {
            $array[] = $nums[$i];
            $this->dfs($i + 1, $nums, $array);
            array_pop($array);
        }
    }}

問題解決のアイデア 2 反復方法

初期化結果は 2 次元の空の配列であり、各要素を反復処理します。各走査中に、結果セットが処理されます。結果セット内の各要素にトラバースされる数が追加され、結果セットの長さは増加し続けます。

class Solution {
  /** 
  * @param Integer[] $nums 
  * @return Integer[][] 
  */
    function subsets($nums) {
        $result = [];
        $result[] = [];
        $numsCount = count($nums);
        for ($i = 0; $i < $numsCount; $i++) {
            $resultCount = count($result);
            for ($j = 0; $j < $resultCount; $j++) {
                $tmp = $result[$j];
                $tmp[] = $nums[$i];
                $result[] = $tmp;
            }
        }
        return $result;
    }}

推奨学習: php ビデオ チュートリアル

以上がバックトラッキングアルゴリズムを使用して PHP のサブセット問題を解決する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。