78. 子集
题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
示例 2：
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同
回溯算法
// 78. 子集
class Solution {
public:
// 主函数，接受一个整数数组作为输入，返回该数组所有可能的子集
vector<vector<int>> subsets(vector<int>& nums) {
backstracking(nums, 0); // 开始回溯算法，从索引0开始
return result; // 返回所有找到的子集
}
private:
vector<vector<int>> result; // 用于存储所有可能的子集
vector<int> path; // 用于存储当前路径（即当前构造的子集）
// 回溯函数
void backstracking(vector<int>& nums, int start) {
// 每次进入函数，先将当前路径添加到结果中
// 因为子集也包括空集和包含部分元素的集合
result.push_back(path);
// 如果start等于nums的大小，说明已经处理完所有元素，返回
if(start == nums.size()) {
return;
}
// 从start开始遍历nums中的每个元素
for(int i = start; i < nums.size(); i++) {
// 将当前元素添加到路径中
path.push_back(nums[i]);
// 递归调用，i+1为下一次递归的起点
backstracking(nums, i + 1);
// 回溯：从路径中移除刚才添加的元素，尝试下一个元素
path.pop_back();
}
}
};
这段代码实现了一个经典的回溯算法框架，用于解决子集生成问题。它首先定义了一个result变量来存储所有可能的子集，以及一个path变量来存储当前正在构建的子集。backstracking是一个递归函数，它试图通过遍历数组nums的每个元素，并在每一步中决定是否将当前元素加入到当前路径path中，从而构建出所有可能的子集。
关键点在于，每次进入backstracking函数时，无论当前路径path的内容如何，都将其添加到结果集result中。这确保了包括空集在内的所有子集都被收集。然后，通过递归地调用自身并逐步增加start参数，算法确保每个元素都有机会被包括在子集中，同时避免了重复。最后，通过在每次递归后从path中移除最近添加的元素，这个算法能够回溯并探索所有可能的子集组合。