题目描述
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note:
The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
Note:
All inputs will be in lowercase. The order of your output does not matter.
解题思路
- 在迭代所有数字时，对于每个新数字，我们可以选择它，也可以不选择它
- 如果选择，只需将当前数字添加到每个现有子集。
- 如果没有选择，只保留所有现有的子集。 我们只是将两者结合起来。
- 例如，{1,2,3}在内部我们有一个结果集合[[]]
- 考虑1，如果不使用它，仍然[]，如果使用1，将它添加到[]，所以我们有[1]现在结合它们，现在我们有[[]，[1]]作为所有可能的子集
- 接下来考虑2，如果不使用它，我们仍然有[[]，[1]]，如果使用2，只需加2到每个前面的子集，我们有[2]，[1,2] 结合它们，现在我们有[[]，[1]，[2]，[1,2]]
- 接下来考虑3，如果不使用它，我们仍然有[[]，[1]，[2]，[1,2]]，如果使用3，只需在每个前面的子集中添加3，我们[[3]， [1,3]，[2,3]，[1,2,3]] 合并它们，现在我们有[[]，[1]，[2]，[1,2]，[3]，[1 ，3]，[2,3]，[1,2,3]]
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
res.push_back({});
for(int i = 0; i < nums.size(); i++){
int size = res.size(); // size 为一个变量，此时res的size，为第二重循环迭代的次数，因为下面还要追加，如果用 res.size() 作为循环条件的话，会造成错误，会报 Memory Exceed Limit
for(int j = 0; j < size; j++){
vector<int> iter = res[j];
iter.push_back(nums[i]); // 选nums[j]，在原有的基础上 追加
res.push_back(iter); // 形成新的vector，push到结果中
}
}
return res;
}
};
