常州网站建设思创网络,网站创建一般创建哪种类型,传奇网页游戏排行榜前十,北京通州网站建设公司给定一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1#xff1a;
输入#xff1a;nums [1,2,3] 输出#xff1a;[[],[1],[2],[1,2],[3…给定一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1
输入nums [1,2,3] 输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
1 nums.length 10 -10 nums[i] 10 nums 中的所有元素 互不相同
解法一如果输入数组大小为n则子集数量为2n^nn我们可以从0循环到2n^nn-1对于循环到的每个数字i其中二进制位为1的位对应输入数组中的元素加入到当前子集中
class Solution {
public:vectorvectorint subsets(vectorint nums) {int sz nums.size();int subSetsNum pow(2, sz);vectorvectorint ans;for (int i 0; i subSetsNum; i) {vectorint cur;for (int j 0; j sz; j) {if ((1 j) i) {cur.push_back(nums[j]);} }ans.push_back(cur);}return ans;}
};如果输入数组大小为n此算法时间复杂度为On*2n^nn空间复杂度为On。
解法二递归处理每处理到一个元素时有两种处理方法将其加入子集或不加入子集
class Solution {
public:vectorvectorint subsets(vectorint nums) {vectorvectorint ans;vectorint current;recursion(0, nums, current, ans);return ans;}private:void recursion(int pos, vectorint nums, vectorint current, vectorvectorint ans) {int sz nums.size();if (pos sz) {ans.push_back(current);return;}// 不加当前位置元素recursion(pos 1, nums, current, ans);// 加当前位置元素current.push_back(nums[pos]);recursion(pos 1, nums, current, ans);current.pop_back();}
};如果输入数组大小为n此算法时间复杂度为On*2n^nn一共有2n^nn种子集每种需要On的时间加入结果数组ans空间复杂度为On主要是栈空间开销和current数组开销。
