《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(53)炼妖壶收子集 - 子集问题(位运算与回溯)
哪吒在数据修仙界中继续他的修炼之旅。这一次,他来到了一片神秘的炼妖壶空间,壶中有一个巨大的炼妖壶,壶身闪烁着神秘的光芒。壶的入口处有一块巨大的石碑,上面刻着一行文字:“欲收此壶,需以炼妖之力,收子集,位运算与回溯显真身。”
哪吒定睛一看,石碑上还有一行小字:“给定集合[1, 2, 3]
,其所有子集为[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
。”哪吒心中一动,他知道这是一道关于生成集合所有子集的难题,需要通过位运算与回溯的方法来解决。
暴力解法:炼妖壶的初次尝试
哪吒心想:“要生成所有子集,我可以逐个元素选择。”他催动炼妖壶之力,通过递归的方式,逐个元素选择或不选择,试图生成所有可能的子集。
vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> result;vector<int> path;backtrack(nums, 0, path, result);return result;
}void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {result.push_back(path);for (int i = start; i < nums.size(); ++i) {path.push_back(nums[i]);backtrack(nums, i + 1, path, result);path.pop_back();}
}
哪吒成功地生成了所有子集,但炼妖壶的光芒却黯淡了下来。他意识到,这种方法虽然可行,但效率低下,尤其是当集合元素很多时,灵力消耗巨大。
C++语法点
在C++中,子集生成问题涉及到递归和回溯。以下是一些重要特性:
-
递归:
- 通过递归函数实现回溯。
- 常用操作:
path.push_back(nums[i])
:将当前元素加入路径。path.pop_back()
:回溯,移除最后一个元素。
-
回溯:
- 通过递归遍历所有可能的选择。
- 常用操作:
backtrack(nums, i + 1, path, result)
:递归调用,从下一个元素开始。
高阶优化:位运算与回溯的智慧
哪吒元神中突然浮现金色铭文——「炼妖壶收子集,位运算与回溯显真身」。他意识到,可以通过位运算优化子集生成过程。
哪吒决定使用位运算,通过遍历所有可能的二进制位组合,生成所有子集。每个二进制位表示是否选择对应元素。通过这种方