1.题目描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例:
2.思路
回溯模板：
result
= []
def backtrack(路径
, 选择列表
):
if 满足结束条件
:
result
.add
(路径
)
return
for 选择
in 选择列表
:
做选择
backtrack
(路径
, 选择列表
)
撤销选择
结果就是树上的所有节点：
3.代码
class Solution {
public:
vector
<vector
<int>> subsets(vector
<int>& nums
) {
if(nums
.empty()){
return res
;
}
vector
<int> track
;
backTrack(nums
, 0, track
);
return res
;
}
void backTrack(vector
<int>& nums
, int start
, vector
<int>& track
){
res
.push_back(track
);
for(int i
= start
; i
< nums
.size(); ++i
){
track
.push_back(nums
[i
]);
backTrack(nums
, i
+ 1, track
);
track
.pop_back();
}
}
private:
vector
<vector
<int>> res
;
};
4.复杂度分析
时间复杂度：
O
(
N
×
2
N
)
\mathcal{O}(N \times 2^N)
O(N×2N)，生成所有子集，并复制到输出集合中。 空间复杂度：
O
(
N
×
2
N
)
\mathcal{O}(N \times 2^N)
O(N×2N)，存储所有子集，共 n 个元素，每个元素都有可能存在或者不存在。
