class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
}
};
面试题 08.04. 幂集
幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。
说明：解集不能包含重复的子集。
示例:
输入： nums = [1,2,3] 输出： [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
原站题解
cpp 解法, 执行用时: 0 ms, 内存消耗: 7.1 MB, 提交时间: 2021-05-31 17:11:10
class Solution {
public:
vector<vector<int>>res;
vector<vector<int>> subsets(vector<int>& nums) {
vector<int>tmp;
dfs(0, tmp, nums);
res.push_back(vector<int>());//别忘了加上空的情况
return res;
}
void dfs(int start, vector<int>& tmp, vector<int>& nums)
{
for (int i = start; i < nums.size(); i++)
{
tmp.push_back(nums[i]);
res.push_back(tmp);
dfs(i+ 1, tmp, nums);//去除多余的排列方式，每次递归循环的开始点为上一次递归点的后一个点
tmp.pop_back();//回溯法的关键就在于每次递归完成以后的弹出元素，还原之前的状态
}
}
};
php 解法, 执行用时: 12 ms, 内存消耗: 15.9 MB, 提交时间: 2021-05-31 16:34:37
class Solution {
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function subsets($nums) {
$n = count($nums);
$size = 1 << $n;
$m = [];
$res = array_fill(0, $n, []);
foreach ( $nums as $i=>$num ) {
$m[1<<$i] = $num;
}
for ( $i = 0; $i < $size; $i++ ) {
$t = $i;
while ( $t > 0 ) {
$c = $t & -$t;
$res[$i][] = $m[$c];
$t -= $c;
}
}
return $res;
}
}