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）
链接：https://leetcode.cn/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路1

子集就是数组中所有元素的集合加上一个空集构成的集合。求解组合和排列实际上就是DFS一棵树的过程。写此类题目画一棵树再根据树来写dfs即可。树可见代码注释。可以看到树的下一层是从上一层的下一个元素开始的。

code

class Solution {
public:
    //组合加上空集就是子集
    //如何求解所有的组合，DFS
    //想想一个求解组合的递归树并通过树来写递归的算法
    //1 -> 2 -> 3
    //  -> 3 
    //2 -> 3
    //3 
    
    vector<vector<int> > ans;
    int n;

    void dfs(vector<int> & nums,int start,vector<int>& path)
    {
        for(int i = start;i < n;i ++)
        {
            path.push_back(nums[i]);
            ans.push_back(path);
            dfs(nums,i + 1,path);
            path.pop_back();        
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        n = nums.size();
        vector<int> path;
        ans.push_back({});
        dfs(nums,0,path);
        return ans; 
    }
};

解题思路2

可以使用二进制位表示当前位置的数组元素是否被选择。比如000表示三个元素都没有被选择，001表示1位置的元素被选择。如果有n位实际上就是有\(2^n-1\)种可能，只需要遍历0-\(2^n-1\)可能性即可。

code

class Solution {
public:
    //位运算：对应位置1即为选用
    //遍历2 ^ n -1 中可能即可


    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        for(int mask = 0;mask < (1 << n);mask ++)
        {
            vector<int> sub;
            for(int i = 0;i < n;i ++)
            {
                if(mask & (1 << i)) sub.push_back(nums[i]);
            }
            ans.push_back(sub);
        }

        return ans;
    }
};