徐老师在那个网站做发视频,搜索引擎优化特点,肇庆市住房和城乡房屋建设局网站,建设部网站施工合同幂集。编写一种方法#xff0c;返回某集合的所有子集。集合中不包含重复的元素。
说明#xff1a;解集不能包含重复的子集。
示例:
输入#xff1a; nums [1,2,3] 输出#xff1a; [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
法一#xff1a;幂集有2的n次…幂集。编写一种方法返回某集合的所有子集。集合中不包含重复的元素。
说明解集不能包含重复的子集。
示例:
输入 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:vectorvectorint subsets(vectorint nums) {int setSize 1 nums.size();vectorvectorint 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 ^n n)一共有2 n ^n n种子集每种需要n的时间来构建空间复杂度为O(1)。
法二递归模拟
class Solution {
public:vectorvectorint subsets(vectorint nums) {vectorvectorint ans;vectorint oneAns;build(0, nums, oneAns, ans);return ans;}private:void build(int index, vectorint nums, vectorint oneAns, vectorvectorint 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 ^n n)空间复杂度为O(n)。
法三先构建一个空集每遍历到一个元素将其加入现有的任意集合都可以构成一个新的集合
class Solution {
public:vectorvectorint subsets(vectorint nums) {vectorvectorint ans;ans.push_back({});for (int i 0; i nums.size(); i){int ansSize ans.size();for (int j 0; j ansSize; j){vectorint temp ans[j];temp.push_back(nums[i]);ans.push_back(temp);}}return ans;}
};如果nums的长度为n此算法时间复杂度为O(2 n ^n n)空间复杂度为O(1)。
