leetcode每日一题之4.子集

子集

方法1：迭代法

即从空数组开始，循环所有的数字，每次往已生成子集的数组后添加数字。得出的就是所有子集，代码如下：

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
   function subsets($nums){
        // 1. 迭代法
        $result = [[]];
        foreach ($nums as $num) {
            foreach ($result as $item) {
                $tmp = $item;
                $tmp[] = $num;
                $result[] = $tmp;
            }
        }

        return $result;
   }
}

方法2：回溯法

参考回溯思想团灭排列、组合、子集问题。

首先先画出回溯树，然后套用公式，代码如下

class Solution {
    protected $result;
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function subsets($nums)
    {
        // 画出递归树，答案是遍历递归树的所有节点
        $this->result[] = [];
        $this->sub($nums, [], 0);
        return $this->result;
    }

    private function sub($nums, $list, $start)
    {
        if (count($list) == count($nums)) {
            return;
        }
        for ($i = $start; $i < count($nums); ++$i) {
            $list[] = $nums[$i];
            // 在这里，递归中途添加，而不是递归终止条件处添加
            $this->result[] = $list;
            $this->sub($nums, $list, $i + 1);
            array_pop($list);
        }
    }
}