PHP 回溯算法求解子集问题

PHP 回溯算法求解子集问题

author: he xiaodong date: 2020-09-21
子集

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

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

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/subsets

解题思路 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 迭代法
  1. 初始化结果为 二维空数组
  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;
    }
}

参考链接

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

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