子集枚举
进阶子集问题把回溯树压缩成最清晰的二叉选择结构。
// 算法讲解
子集枚举
每个元素「选或不选」，观察二叉决策树的展开过程。
待机
速度 中
待机 ⌨1vector<int> subset;
2
3void dfs(int idx, const vector<int>& nums) {
4 if (idx == (int)nums.size()) {
5 return;
6 }
7 dfs(idx + 1, nums);
8 subset.push_back(nums[idx]);
9 dfs(idx + 1, nums);
10 subset.pop_back();
11}
复杂度分析
时间 O(n * 2^n)
空间 O(n)
最优 O(1)
最坏 O(n * 2^n)
算法讲解
对子集问题来说，每个元素都只有两个决策：加入当前集合，或跳过它。
这让递归树天然长成一棵二叉树，非常适合初学者理解状态分叉。
如果再叠加去重、和约束、大小约束，就能衍生出组合总和、子集 II 等很多经典题。
它也是理解位运算枚举和 DFS 枚举之间关系的好入口。