[LeetCode] 78. 子集

题目描述；

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

题目链接：

. - 力扣（LeetCode）

解题主要思路：

其实这道题，第一次写的话，不动手画个决策树还真的挺容易出错的。我们可以画个决策树，根节点为空（第1层），根节点除外，每层的节点为上一层的节点再选择是否插入nums。

以nums:[1,2,3]为例，第一层是空，第二层的话的节点有第一层的节点插入“1”，得到两个节点：[]和[1]，第三层的节点分别为第二层的节点再选择是否插入“2”，第四层同理。

当我们要插入的数的下标 i == nums.size()时，说明遍历完了，此时需要将结果插入到ret中。

解题代码：

class Solution {
public:
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        dfs(nums, 0);
        return ret;
    }
    void dfs(vector<int>& nums, int pos)
    {
        // 结束条件
        if (pos == nums.size()) {
            ret.push_back(path);
            return;
        }
        // 选
        path.push_back(nums[pos]);
        dfs(nums, pos+1);
        path.pop_back();  // 恢复原本的path
        // 不选
        dfs(nums, pos+1);
    }
};