两种方法
子集是求组合数。46题 47题是求排列数
第一种循环
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
res.push_back({});
for(auto x: nums)
{
int len = res.size();
for(int i = 0; i < len; i++)
{
auto tmp = res[i];
tmp.push_back(x);
res.push_back(tmp);
}
}
return res;
}
};
第二次写题
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
res.push_back({});
for(int i = 0; i < nums.size(); i++)//遍历每一个数字
{
int n = res.size();
for(int j = 0; j < n; j++)
{
vector<int> tmp = res[j];
tmp.push_back(nums[i]);
res.push_back(tmp);
}
}
return res;
}
};
第二种dfs
class Solution {
vector<vector<int>> res;
vector<int> nums;
void dfs(long long idx)
{
if(idx == nums.size())
return;
int len = res.size();
for(int i = 0; i < len; i++)
{
auto tmp = res[i];
tmp.push_back(nums[idx]);
res.push_back(tmp);
}
dfs(idx + 1);
}
public:
vector<vector<int>> subsets(vector<int>& _nums) {
nums = _nums;
res.push_back({});
dfs(0);
return res;
}
};
第三次写题
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res = {{}};
for(int i = 0; i < nums.size(); i++)
{
int len = res.size();
for(int j = 0; j < len; j++)
{
auto tmp = res[j];
tmp.push_back(nums[i]);
res.push_back(tmp);
}
}
return res;
}
};