本文共 1003 字,大约阅读时间需要 3 分钟。
本系列文章已全部上传至我的github,地址:
欢迎大家关注我的新浪微博, 欢迎转载,转载请注明出处
Given a set of distinct integers, nums, return all possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:[
[3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
本题大意:给定一个数集,计算得出它的所有子集
需要注意一下几点:
1、子集不能重复
2、子集里面的数需要按照非降序排列
解题思路:考虑到用位操作来模拟所有的排列组合。以数集大小等于3为例:
3位二进制的全排列为:000,001,010,011,100,101,111
利用这个全排列,为1就选入子集,为0就不选。很容易就得到了所有子集
class Solution {public: vector> subsets(vector & nums) { long n = pow(2,nums.size());//按位数得到全排列最大值 sort(nums.begin(),nums.end());//由于子集的数需要按非降序排列,故先将集合排序 vector > ret; for(long i = 0 ; i < n ; i++) { vector tempset; for(int j = 0 ; j < nums.size() ;j++) { if((i>>j)&1==1)//判断每一位是否为1 { tempset.push_back(nums[j]); } } ret.push_back(tempset); } return ret; }};