[LeetCode 78]PHP 回溯算法求解子集问题

码农天地 - 2020-09-22 23:08:41

原文链接：何晓东博客

子集

给定一组不含重复元素的整数数组 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;

     }

}

参考链接

回溯算法团灭排列/组合/子集问题

最后恰饭阿里云全系列产品/短信包特惠购买中小企业上云最佳选择阿里云内部优惠券

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。