文章目录 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）一、问题描述**方法一：递归****方法二：深度优先遍历****方法三：循环遍历枚举****方法四：位运算****方法五：层序遍历**
一、问题描述 题目：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]输出:[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []] 方法一：递归 class Solution {public: vector<vector<int>> findsubsets(vector<int>& nums, int k){ vector<vector<int>> result; //主要思想是递归：如果你知道前k - 1个元素的所有子集，那么整个数组的子集就是往前k - 1个元素的所有子集的尾部在push第k个元素，当数组中没有元素时，在push一个空集 //递归出口是当k == 0 时，往result中放一个空集，空集是任何数组的子集 if(k==0) { result.push_back({}); } else { vector<vector<int>> lastresult = findsubsets(nums, k-1);//进入递归 result = lastresult;//保存当前的所有子集 for(int i = 0; i < lastresult.size(); i++) { lastresult[i].push_back(nums[k-1]); //把每个子集尾部push第k-1个元素作为新的子集，继续放到result数组中 result.push_back(lastresult[i]); } } return result; } vector<vector<int>> subsets(vector<int>& nums) { return findsubsets(nums,nums.size()); }};原理解释：
集合的每个元素，都有可以选或不选，用二进制和位运算，可以很好的表示
vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res ; for (int i = 0; i < (1 << nums.size()); i++) { vector<int> sub ; for (int j = 0; j < nums.size(); j++) if (((i >> j) & 1) == 1) sub.push_back(nums[j]); res.push_back(sub); } return res; }}; 方法五：层序遍历把整个当作二叉树，进行层序遍历
class Solution3 {public: struct result { vector<int> res; int pos; bool used; }; vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; if(nums.size()==0) return res; queue<result> queue; queue.push({vector<int>(),0,true}); queue.push({vector<int>(),0,false}); while(!queue.empty()) { result node = queue.front(); queue.pop(); if(node.pos==nums.size()-1) { if(node.used) node.res.push_back(nums[node.pos]); res.push_back(node.res); continue; } else { if(node.used) node.res.push_back(nums[node.pos]); queue.push({node.res,node.pos+1,true}); queue.push({node.res,node.pos+1,false}); } } return res; }};