26
05/2015
[LeetCode] Subsets
Subsets
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], [] ]
解题思路：
题意为找出一个集合的所有子集。题目要求结果中所有子集的元素升序排列，所以先将原来集合排序。然后通过递归回溯的方法枚举出所有子集。注意边界条件的判断。这里当下标大于数组的大小，就返回。每次我都会错一下。LeetCode运行时间4ms
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
vector<vector<int>> result;
vector<int> item;
subsetsHelper(result, nums, item, 0);
return result;
}
void subsetsHelper(vector<vector<int>>& result, vector<int>& nums, vector<int>& item, int index){
if(index>nums.size()){
return;
}
result.push_back(item);
for(int i=index; i<nums.size(); i++){
item.push_back(nums[i]);
subsetsHelper(result, nums, item, i+1);
item.pop_back();
}
}
};另外一种解法，可以用一个二进制来表示取哪些数。我们知道，一个n大小的集合的子集个数为2^n。从0枚举到2^n-1。然后通过位运算来检查哪些位为1即可。时间复杂度比上述方法大些。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
std::sort(nums.begin(), nums.end());
vector<vector<int>> result;
int len = nums.size();
double subsetNum = pow(2, len);
for(int i=0; i<subsetNum; i++){
vector<int> item;
int j=0;
int k=i;
while(k!=0){
if(k&1){
item.push_back(nums[j]);
}
k = k>>1;
j++;
}
result.push_back(item);
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Subsets
0 条评论