LeetCode 面试题08.04.幂集

本文主要是介绍LeetCode 面试题08.04.幂集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

幂集。编写一种方法，返回某集合的所有子集。集合中不包含重复的元素。

说明：解集不能包含重复的子集。

示例:

输入： 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(n2${}^n$)，一共有2${}^n$种子集，每种需要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(n2${}^n$)，空间复杂度为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(2${}^n$)，空间复杂度为O(1)。

这篇关于LeetCode 面试题08.04.幂集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---