38
PHP 回溯算法求解子集问题
source link: http://hxd.best/2020/09/21/PHP-回溯算法求解子集问题/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
子集
给定一组不含重复元素的整数数组 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;
}
}
参考链接
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK