关于php:LeetCode-78PHP-回溯算法求解子集问题

41次阅读

共计 996 个字符，预计需要花费 3 分钟才能阅读完成。

原文链接：何晓东博客

子集

给定一组 不含反复元素 的整数数组 nums，返回该数组所有可能的子集（幂集）。

阐明：解集不能蕴含反复的子集。

示例:


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

输入:

[[3],

 [1],

 [2],

 [1,2,3],

 [1,3],

 [2,3],

 [1,2],

 []]

起源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl…

解题思路 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;

     }

}

参考链接