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 中的所有元素 互不相同

Related Topics

位运算

数组

回溯

参考leetcode视频讲解：

开始假设输出子集为空。

遍历数组，对于数组中的每一个整数，每一步都向输出子集中所有子集添加这个整数，并生成新的子集。

public List> subsets(int[] nums) {
    List> result = new ArrayList<>();
    result.add(new ArrayList<>()); // 空集
    int length = nums.length;
    for(int i = 0 ; i < length;i++){
        
        List> newResult = new ArrayList<>();
        //往原来的子集中添加数字
        for(int j = 0; j < result.size();j++){
            List temp = new ArrayList<>(result.get(j));
           temp.add(nums[i]);
           newResult.add(temp);
        }
        result.addAll(newResult);
    }
    return result;
}
解答成功:
            执行耗时:0 ms,击败了100.00% 的Java用户
            内存消耗:41.3 MB,击败了7.48% 的Java用户

数字总数为n，子集中每个数字的状态有2种，在子集中(1)和不在子集中(0)。刚好对应的是0~2^n-1。

public List> subsets(int[] nums) {
    List> result = new ArrayList<>();
​
    int length = nums.length;
    int size = 1 << length;
    //总共有2^length个 遍历
    for(int i = 0 ; i < size;i++){
        List list = new ArrayList<>();
​
        for(int j = 0;j < length;j++){
            if((i & (1 << j)) != 0){
                list.add(nums[j]);
            }
        }
        result.add(list);
    }
    return result;
}