题目描述：
给出一个整数数组nums，长度为 $ n $ ，数组中的元素互不相同。返回该数组所有可能的子集。
解集中不能包含重复的子集。可以按照任意顺序返回解集。
数据范围：
$ 1\le n \le 10 $
题解：
解法有很多种。
- 使用迭代法，从答案的视角，选哪个数。使用
for需要枚举每一次能选的数字。 - 直接递归法，从输入的视角，对于每个数来说，选于不选。不在
dfs中使用循环，只枚举选当前数或者不选当前数。 - 使用二进制枚举，因为子集的数量是 $ 2^n $ ，并且也刚好符合二进制的特征。判断该 $ j $ 位是否为 $ 1 $ ，
mask & (1 << j)。
代码：
解法1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
vector<vector<int>> subsets(vector<int> &nums)
{
int n = nums.size();
vector<vector<int>> ret;
vector<int> cur;
function<void(int)> dfs = [&](int step)
{
ret.push_back(cur);
for (int i = step; i < n; ++i)
{
cur.push_back(nums[i]);
dfs(i + 1);
cur.pop_back();
}
};
dfs(0);
return ret;
}
};
|
解法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
void dfs(int step, vector<int> &nums, vector<int> &cur)
{
if (step == nums.size())
{
ans.emplace_back(cur);
return;
}
cur.emplace_back(nums[step]);
dfs(step + 1, nums, cur);
cur.pop_back();
dfs(step + 1, nums, cur);
}
vector<vector<int>> subsets(vector<int> &nums)
{
vector<int> cur;
dfs(0, nums, cur);
return ans;
}
};
|
解法3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
vector<vector<int>> ans;
vector<vector<int>> subsets(vector<int> &nums)
{
vector<int> cur;
for (int i = 0; i < (1 << nums.size()); ++i)
{
cur.clear();
for (int j = 0; j < nums.size(); ++j)
{
if (i & (1 << j))
{
cur.emplace_back(nums[j]);
}
}
ans.emplace_back(cur);
}
return ans;
}
};
|