幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
法一:幂集有2的n次方个,我们可以从0开始循环到2的n次方减1,每次循环生成一个幂集,方法是数字中为1的位对应位置的数放入当前幂集中:
class Solution {public:vector<vector<int>> subsets(vector<int>& nums) {int setSize = 1 << nums.size();vector<vector<int>> ans;for (int i = 0; i < setSize; ++i){ans.push_back({});for (int j = 0; j < nums.size(); ++j){if (i & (1 << j)){ans.back().push_back(nums[j]);}}}return ans;}};
如果nums的长度为n,此算法时间复杂度为O(n2n ^nn),一共有2n ^nn种子集,每种需要n的时间来构建;空间复杂度为O(1)。
法二:递归模拟:
class Solution {public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> oneAns;build(0, nums, oneAns, ans);return ans;}private:void build(int index, vector<int> &nums, vector<int> &oneAns, vector<vector<int>> &ans){if (index == nums.size()){ans.push_back(oneAns);return;}oneAns.push_back(nums[index]);build(index + 1, nums, oneAns, ans);oneAns.pop_back();build(index + 1, nums, oneAns, ans);}};
如果nums的长度为n,此算法时间复杂度为O(n2n ^nn),空间复杂度为O(n)。
法三:先构建一个空集,每遍历到一个元素,将其加入现有的任意集合都可以构成一个新的集合:
class Solution {public:vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;ans.push_back({});for (int i = 0; i < nums.size(); ++i){int ansSize = ans.size();for (int j = 0; j < ansSize; ++j){vector<int> temp = ans[j];temp.push_back(nums[i]);ans.push_back(temp);}}return ans;}};
如果nums的长度为n,此算法时间复杂度为O(2n ^nn),空间复杂度为O(1)。