LeetCode 78. 子集（回溯）
LeetCode 78. 子集（回溯）
Michael阿明
发布于 2021-02-20 11:10:23
发布于 2021-02-20 11:10:23
代码可运行
运行总次数：0
代码可运行
1. 题目信息
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 暴力回溯
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> sub;
vector<vector<int>> ans;
bt(nums, sub, ans, 0);
return ans;
}
void bt(vector<int>& nums, vector<int> sub, vector<vector<int>> & ans, int i)
{
if(i == nums.size())
{
ans.push_back(sub);
return;
}
bt(nums, sub, ans, i+1);//不加入nums[i]
sub.push_back(nums[i]);
bt(nums, sub, ans, i+1);//加入nums[i]
}
};or
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> sub;
vector<vector<int>> ans;
ans.push_back({});
bt(nums,sub,ans,0);
return ans;
}
void bt(vector<int>& nums,vector<int> sub, vector<vector<int>> &ans, int i)
{
for(int idx = i; idx < nums.size(); ++idx)
{
sub.push_back(nums[idx]);
ans.push_back(sub);
bt(nums,sub,ans,idx+1);
sub.pop_back();
}
}
};2.2 循环
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
ans.push_back({});
vector<int> sub;
int i, j, n;
for(i = 0; i < nums.size(); ++i)
{
n = ans.size();//注意提前记录size
for(j = 0; j < n; ++j)
{
sub = ans[j];
sub.push_back(nums[i]);
ans.push_back(sub);
}
}
return ans;
}
};2.3 位运算
- 对例子来讲，一共8种情况，对应的二进制位：
000,001,010,011,100,101,110,111 - 每次内层循环，把为1的位对应的数字取出来，就是所有组合
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
int i, j, k = pow(2,nums.size());
for(i = 0; i < k; ++i)
{
vector<int> sub;
for(j = 0; j < nums.size(); ++j)
{
if(i & (1<<j))
sub.push_back(nums[j]);
}
ans.push_back(sub);
}
return ans;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/29 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
