78. 子集

曾经终败给现在 2023-02-08 12:44 15阅读 0赞

题目链接：https://leetcode-cn.com/problems/subsets/

> 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
> 
> 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

方法一：二进制判断 + 迭代  
思路：用一个 n 位二进制数标记哪些元素将构成子集，其中 n 是原数组的长度。  
实现：

class Solution {
        
        public List<List<Integer>> subsets(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
    
            // 对 n 位二进制数遍历
            for (int i = 0; i < (1 << nums.length); i++ ) {
        
                
                List<Integer> sub = new ArrayList<>();
    
                // 对原数组进行遍历
                for (int j = 0; j < nums.length; j++)  {
        
                    // 位运算、与运算 判断下标为 j 的元素是否放到子集
                    if ( ((i >> j) & 1) == 1  ) sub.add(nums[j]);
                }
                res.add(sub);
            }
    
            return res;
        }
    }

复杂度分析

*  时间复杂度：O(n \* 2^n)  
    第一层循环 2^n ，第二层循环 n
 *  空间复杂度：O(n) 构造临时数组需要 n 的空间

推荐题解：  
https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/  
https://leetcode-cn.com/problems/subsets/solution/er-jin-zhi-wei-zhu-ge-mei-ju-dfssan-chong-si-lu-9c/

方法二：递归（二叉树的中序遍历）  
思路：数组中每个元素的选和不选，构成了一个满二叉状态树，比如，左子树是选，右子树是不选，从根节点、到叶子节点的所有路径，构成了所有子集。可以有前序、中序、后序的不同写法，结果的顺序不一样。

实现：  
这里采用中序遍历

class Solution {
        
    	// 把子集和结果集定义为成员变量，递归函数就不用传那么多参数了
        List<Integer> sub = new ArrayList<Integer>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
    
    
        public List<List<Integer>> subsets(int[] nums) {
        
            dfs(0, nums);
            return ans;
        }
    
        private void dfs(int i, int[] nums) {
        
            if (i == nums.length) {
        
                // 深拷贝 子集的元素
                ans.add(new ArrayList<>(sub));
                return;
            }
    
            // 左子树，选择元素
            sub.add(nums[i]);
            dfs(i+1, nums);
    
            // 递归完左子树回到当前节点，去掉本元素，然后遍历右子树
            sub.remove(sub.size()-1);
            dfs(i+1, nums);
    
        }
    }

复杂度分析

时间复杂度：O(n \* 2^n)  
一共有2^n种状态（2 ^ n 个叶子节点），每种状态需要O(n)的时间来构造子集（从根节点到叶子节点需要 O(n) 的复杂度）  
空间复杂度：O(n)  
构造临时数组需要 n 的空间，递归时栈的深度需要 n 的空间。

推荐题解：  
https://leetcode-cn.com/problems/subsets/solution/er-jin-zhi-wei-zhu-ge-mei-ju-dfssan-chong-si-lu-9c/