198.回溯算法：子集（力扣）

代码解决

class Solution {
public:
    // 用于存储当前子集的临时向量
    vector<int> res;
    // 用于存储所有子集的结果向量
    vector<vector<int>> result;
 
    // 回溯函数
    void backtracing(vector<int>& nums, int index) {
        // 每次递归调用都将当前子集添加到结果中
        result.push_back(res);
 
        // 如果当前索引超过了数组的大小，返回
        if (index >= nums.size()) {
            return;
        }
 
        // 遍历从当前索引到数组末尾的所有元素
        for (int i = index; i < nums.size(); i++) {
            // 将当前元素添加到临时子集中
            res.push_back(nums[i]);
            // 递归调用，处理下一个元素
            backtracing(nums, i + 1);
            // 回溯，移除最后添加的元素，继续处理下一个可能的子集
            res.pop_back();
        }
    }
 
    // 主函数，生成所有子集
    vector<vector<int>> subsets(vector<int>& nums) {
        // 从第0个元素开始回溯
        backtracing(nums, 0);
        // 返回所有生成的子集
        return result;
    }
};

过程描述

假设输入数组为[1, 2, 3]，代码生成子集的过程如下：

1. 初始化空子集并添加到结果中：[]
2. 从第一个元素开始，添加1，递归生成子集：[1]
   • 添加到结果中：[[], [1]]
   • 继续添加2，递归生成子集：[1, 2]
     • 添加到结果中：[[], [1], [1, 2]]
     • 继续添加3，递归生成子集：[1, 2, 3]
       • 添加到结果中：[[], [1], [1, 2], [1, 2, 3]]
     • 回溯，移除3，继续处理其他可能的子集
   • 回溯，移除2，继续处理其他可能的子集
     • 添加3，递归生成子集：[1, 3]
       • 添加到结果中：[[], [1], [1, 2], [1, 2, 3], [1, 3]]
3. 回溯，移除1，继续处理其他可能的子集
   • 添加2，递归生成子集：[2]
     • 添加到结果中：[[], [1], [1, 2], [1, 2, 3], [1, 3], [2]]
     • 继续添加3，递归生成子集：[2, 3]
       • 添加到结果中：[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3]]
   • 回溯，移除2，继续处理其他可能的子集
     • 添加3，递归生成子集：[3]
       • 添加到结果中：[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]