子集
给定一组不含重复元素的整数数组 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 迭代法
- 初始化结果为 二维空数组
- 遍历给定数组中的每一个元素,在每一次遍历中,处理结果集。结果集中的每个元素添加遍历到的数字,结果集的长度不断增加。
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;
}
}
参考链接