LeetCode 78 子集

Posted on 2020-09-20  135 Views


题目链接

给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

题解

第一想法是按长度枚举,不过后来发现没办法列出所有情况,看了下官方题解才知道可以按照二进制枚举。

官方题解:

方法一:迭代法实现子集枚举

0/1 序列子集0/1 序列对应的二进制数
000{}0
001{9}1
010{2}2
011{2,9}3
100{5}4
101{5,9}5
110{5,2}6
111{5,2,9}7

复杂度分析:

  • 时间复杂度: O(n \times 2^n)
    一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。
  • 空间复杂度: O(n)
    即构造子集使用的临时数组的空间代价。
迭代
class Solution {

    fun subsets(nums: IntArray): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        val len = nums.size
        for (i in 0..1.shl(len)-1) { //0~2^n-1
            val list = mutableListOf<Int>()
            for (j in 0..len-1) {   //每一位
                if (i.and(1.shl(j)) != 0)   // &位运算,获取每一位不为0的数
                    list.add(nums[j])
            }
            ans.add(list)
        }
        return ans
    }
}

方法二:递归法实现子集枚举

复杂度分析

  • 时间复杂度:O(n \times 2^n)
    一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。
  • 空间复杂度:O(n)
    临时数组的空间代价是O(n),递归时栈空间的代价为O(n)
递归
class Solution {

    val ans = mutableListOf<List<Int>>()
    val list = mutableListOf<Int>()
    fun subsets(nums: IntArray): List<List<Int>> {
        dfs(0,nums)
        return ans
    }

    fun dfs(cur:Int, nums: IntArray){
        if (cur==nums.size){
            val tmp = list.toList()
            ans.add(tmp)
            return
        }
        list.add(nums[cur])
        dfs(cur+1,nums)
        list.removeAt(list.size-1)
        dfs(cur+1,nums)
    }
}

隐约雷鸣 阴霾天空 但盼风雨来 能留你在此