PHP如何用回溯演算法求解子集問題

回溯演算法其實一個類似枚舉的搜尋嘗試過程，主要是在搜尋嘗試過程中尋找問題的解，當發現已不滿足求解條件時，就「回溯」返回，嘗試別的路徑。回溯法是一種選優搜尋法，依選優條件向前搜索，以達到目標。

當探索到某一步時，發現原先選擇並不優或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態的點稱為「回溯點」。許多複雜的，規模較大的問題都可以使用回溯法，有「通用解題方法」的美稱。

子集

給定一組不含重複元素的整數陣列 nums，傳回該陣列所有可能的子集（冪集）。

說明：解集不能包含重複的子集。

範例:

输入: 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 迭代法

#初始化結果為二維空數組遍歷給定數組中的每一個元素，在每一次遍歷中，處理結果集。結果集中的每個元素添加遍歷到的數字，結果集的長度不斷增加。

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中文網其他相關文章！